树状数组

首要用途：维护序列的前缀和

对一个序列a，建立一个数组c，其中c[x]保存序列a的区间(x-lowbit(x)+1,x]中所有数的和(前开后必)。

性质：

1.每一个节点x，有c[x]保存着以x为根节点的所有叶节点的和

2.每个内部节点c[x]的子节点个数等于lowbit（x）的位数

3.除了树根以外的每个子节点的父节点都是c[x+lowbit(x)];

4.数的深度为log(N) //N为序列a的长度

tips

1. O(logN)的时间复杂度去实现单点修改和区间查询
2. 数组下标一定要从1开始
3. 一个数的二进制表示中末尾有几个0就在第几层

lowbit

x & (-x) : 假设 x的二进制数表示 的从右向左数的第一个1所在位为k，则lowbit(x) = 2^(k-1)

tip: 求 n 的二进制表示的第 k 位(从0开始)数字：n >> k & 1

功能

1. 实现单点修改
2. 实现求前缀和

代码示例

// 构造树状数组的方法
// 可以假设原序列a为全0，依次通过“单点修改”操作把每个数加进去，最后就可以形成树状数组了
#include <bits/stdc++.h>
 
using namespace std;

const int N = 1e5+10;

int n,m;
int t[N],tr[N];

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

//在原数组的第x个数加上v
void add(int x,int v){
    //注意这里的i是从x开始得
    for(int i=x;i<=n;i+=lowbit(i)){ 
        tr[i] += v; //在树状数组第i个位置上加上一个值
    }
}

//返回原数组前x个数的前缀和
int query(int x){
    int sum = 0;
    for(int i=x; i>0; i-=lowbit(i)){
        sum += tr[i];
    }
    return sum;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> t[i];
    }
    for(int i=1;i<=n;i++){
        add(i,t[i]); //在第i个位置上加上原数组t[i] 构造树状数组
    }
    while(m--){
        int sum=0;
        int k,x,y;
        cin >> k >> x >> y;
        if(k == 0){
            cout << query(y) - query(x-1) << endl; //求的是[a,b]的必区间
        }
        else{
            add(x,y);
        }
    }
    return 0;
}