什么是樹狀數組？

?樹狀數組就是通過數組來模擬一種樹形結構，這種樹形結構能夠維護區間信息。同樣類似的數據結構還有線段樹，線段樹與樹狀數組相比，它的結點更多，也就是說線段樹的常數更大。

?線段樹是通過把區間二分來維護區間的信息，而樹狀數組是通過lowbit來維護區間的信息。

?以樹狀數組維護區間和為例，對于樹狀數組c而言，$ c[i]= a[i-2k+1]+a[i-2k+2]+...+a[i]$ ,其中數組a存儲的是數據，k就是lowbit位。

?lowbit: 一個非零二進制數中最小的不為零的位。

C++板子

#include

using namespace std;

/**

以維護區間和的場景為例

**/

const int N = 1e5+2;

int a[N],b[N];

int lowbit(int x) { return x & (-x); }

/*

區間查詢，單點修改

*/

int query(int x) {

int ret = 0;

for(int i=x;i;i-=lowbit(i)){

ret += b[i];

}

return ret;

}

void add(int x,int d) {

for(int i=x;i<=n;i+=lowbit(i)) {

b[i]+=d;

}

}

int main() {

//先把每個點的信息添加到樹狀數組內

for(int i=0;i

cin >> a[i];

add(i,a[i]);

}

//查詢區間[a,b]的內容

cout << query(b) - query(a-1);

}

JAVA板子

public class Main {

public static void main(String[] args) {

}

private static int lowbit(int x) {

return x & (-x);

}

private static class binary_indexed_tree {

private int n;

private int a[];

private int b[];

public binary_indexed_tree() {

binary_indexed_tree(1000);

}

public binary_indexed_tree(int n) {

a = new int[n];

b = new int[n];

this.n = n;

}

// 單點修改

public void add(int x,int d) {

for(int i=x;i<=n;i+=lowbit(i)) {

b[i] += d;

}

}

//區間查詢

public int query(int x) {

int ret = 0;

for(int i=x ;i; i-=lowbit(i)) {

ret += b[i];

}

return ret;

}

}

//區間修改，單點查詢，本質是利用差分的思想。

//其中b[]是a[]的差分數組

public void test() {

binary_indexed_tree2 tree = new binary_indexed_tree2();

for(int i=0;i

a[i]=in.nextInt();

tree.add(i,a[i]-a[i-1]);

}

//區間修改，比如在(l,r)區間增加d

tree.add(l,d);

tree.add(r+1,-d);

//單點查詢x

System.out.println(tree.query(x));

}

public static class binary_indexed_tree2 {

private int n;

private int a[];

private int b[];

public binary_indexed_tree2() {

binary_indexed_tree2(1000);

}

public binary_indexed_tree2(int n) {

a = new int[n];

b = new int[n];

this.n = n;

}

//單點修改

public void add(int x,int d) {

for(int i=x;i>0;i-=lowbit(i)) {

b[i]+=d*(lowbit(i));

}

}

//區間查詢

public int change(int x) {

int ret = 0;

for(int i=x;i>=0;i-=lowbit(i)) {

ret += b[i];

}

return ret;

}

}

// 區間查詢，區間修改

// 差分數組前n項的前n項和

public static class binary_indexed_tree3 {

private int n;

private int a[];

private int b[];

private int c[];

public binary_indexed_tree2() {

binary_indexed_tree2(1000);

}

public binary_indexed_tree2(int n) {

a = new int[n];

b = new int[n];

this.n = n;

}

public void add(int x,int y,int d) {

add2(x,d,b);

add2(y+1,-d,b)

add2(x,(x-1)*d,c);

add2(y+1,-d*(y),c);

}

public int query(int x,int y) {

int rx = get(x-1,b)*(x-1)-get(x-1,c);

int ry = get(y,b)*y-get(y,c);

return ry-rx;

}

public void add(int x,int d,int []arr) {

for(int i=x;i<=n;i+=lowbit(i))

arr[i]+=d;

}

public int get(int x,int []arr) {

int ret = 0;

for(int i=x;i;i-=lowbit(x)) {

ret +=arr[i];

}

return ret;

}

}

}

總結

以上是生活随笔為你收集整理的树状数组 java_算法模板之树状数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。