引言

树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构．

原理

其工作原理如下：

再学习树状数组前要先引入一个操作lowbit：

记𝑥 二进制最低位 1 以及后面的 0 组成的数为 lowbit⁡(𝑥)。

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

则在数组中：

• c[x]的长度为lowbit(x)
• c[x]的父节点为c[x+lowbit(x)]

实现

对此可以得出数组中的两个操作：

单点更新：

void add(int x,int n){
    while(x<c.size()){
        c[x]+=n;
        x+=lowbit(x);
    }
}

区间查询：

int ask(int x){
    int res=0;
    while(x){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

进阶

传统的树状数组只支持单点修改。如果题目要求区间修改（例如：将 $[l, r]$ 全都加上 $d$），我们可以引入 差分数组 的思想：

1. 建立原数组 $a$ 的差分数组 $b[i] = a[i] - a[i-1]$。
2. 区间修改 $[l, r] + d \implies$ add(l, d) 和 add(r + 1, -d)。
3. 单点查询 $a[x] \implies$ ask(x)（即差分数组的前缀和）。