树状数组

模板

#include<cstdio>

#define N 500001
using namespace std;

inline int lowbit(int x){
    return x&-x;
}
int n,m,a[N],c[N];
void update(int x,int k){
    while(x<=n){
        c[x]+=k;
        x=x+lowbit(x);
    }
}

int query(int r){
    int ans=0;
    while(r>=1){
        ans+=c[r];
        r=r-lowbit(r);
    }
    return ans;
}

int main(){
    int t,s,opt;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&t);
        update(i,t);
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d",&s,&t);
            update(s,t);
        }else{
            scanf("%d%d",&s,&t);
            printf("%d\n",query(t)-query(s-1));
        }
    }
}

适用场景

前提

• 结合律：(x\circ y)\circ z=x\circ(y\circ z)，其中 \circ 是一个二元运算符。

• 可差分：具有逆运算的运算，即已知 x\circ y 和 y 可以求出 x。

题目要求

• 区间修改、单点查询（配合差分）

• 单点修改、区间查询

原理

通过树状数组的英文名（BIT, Binary Index Tree）很好理解，其实是通过二进制把区间划分成小段，例如区间右边界是 41(101001)_2, 各段长度就是 1,8,32，也就是不断地把最后一位的1剥离出来。

性质

1. 对于 x\le y ，要么有 c[x] 和 c[y] 不交，要么有 c[x] 包含于  c[y]。