【算法模板】数据结构：树状数组

【算法模板】数据结构：树状数组

概念

树状数组(Binary Indexed Trees)其基本用途是维护序列的前缀和。对于给定的序列a，我们建立一个数组C，其中c[x]保存序列a的区间[x-lowbit(x)+1,x]中所有数的和。 事实上，数组c可以看作一个如下图所示的树形结构，图中最下边一行是N个叶节点(N=16),代表数值a[1~N]。该结构满足以下性质:

1. 每个内部节点c[x]保存以它为根的子树中所有叶节点的和；
2. 每个内部节点c[x]的子节点个数等于lowbit(x)的位数；
3. 除树根外，每个内部节点C[x]的父节点是c[x+lowbit(x)];
4. 树的深度为0(log N)。

如果N不是2的整次幂，那么树状数组就是一个具有同样性质的森林结构。

模板

#define lowbit(x) (x&(-x))
void add(int x, int y) {
	for (; x <= n; x += lowbit(x))trr[x] += y;
}
long long ask(int x) {
	long long ans = 0;
	for (; x; x -= lowbit(x))ans += trr[x];
	return ans;
}
1
2
3
4
5
6
7
8
9

例题

单点修改，区间查询

单点修改，区间查询 - 蓝桥云课 (lanqiao.cn)

#include <bits/stdc++.h>
using namespace std;

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

void add(vector<int>& trr,int p,int v){
    for(int i=p;i<trr.size();i+= lowbit(i))trr[i]+=v;
}

int find(vector<int>& trr,int p){
    int sum=0;
    for(int i=p;i;i-= lowbit(i))sum+=trr[i];
    return sum;
}

int main(){
    int n;cin>>n;
    vector<int> arr(n+1);
    vector<int> trr(n+1);
    for(int i=1;i<=n;i++)cin>>arr[i];
    for(int i=1;i<=n;i++)arr[i]+=arr[i-1];
    int m;cin>>m;
    while(m--){
        int choice;cin>>choice;
        if(choice==1) {
            int x, a;
            cin >> x >> a;
            add(trr, x, a);
        }
        else{
            int a,b;cin>>a>>b;
            cout<<find(trr,b)-find(trr,a-1)
            +arr[b]-arr[a-1]<<endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

区间修改、区间求和

#include <bits/stdc++.h>
using namespace std;
#define int long long

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

void add(vector<int>& trr,int p,int v){
    for(int i=p;i<trr.size();i+= lowbit(i))trr[i]+=v;
}

int find(vector<int>& trr,int p){
    int sum=0;
    for(int i=p;i;i-= lowbit(i))sum+=trr[i];
    return sum;
}

signed main() {
    int n,m;
    cin >> n>>m;
    vector<int> arr(n + 1);
    vector<int> trr(n + 1);
    for (int i = 1; i <= n; i++)cin >> arr[i];
    while (m--) {
        int choice;
        cin >> choice;
        if (choice == 1) {
            int l, r, a;
            cin >> l >> r >> a;
            add(trr, l , a);
            if (r + 1 <= n) add(trr, r + 1, -a);
        } else {
            int x;
            cin >> x;
            cout << arr[x]+find(trr, x)  << endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38