树状数组

树状数组相比于线段树类的操作，支持单点修改与区间查询，代码量小于线段树类的一种精简算法

普通的树状数组可以维护满足结合律且可以差分运算的信息

树状数组的每个元素表示它管辖范围内的元素总值，（前缀和，乘积，异或等）

相比于线段树的每个父节点管辖两个儿子，树状数组允许一个父节点管辖多个儿子节点

*图片引自OIWIKI

初始化树状数组定义，这里以维护前缀和信息为例

int n,m;//n个数，m个询问
int a[N],s[N];//a存元素，s记录树状数组维护的信息

那么如何计算一个节点的父节点是谁呢？树状数组的核心在于爬链操作，利用lowbit进行运算

假设一个节点的编号为 $x$ ，那么它的父节点编号为 $x+lowbit(x)$

这里定义的 lowbit 不是常规定义的最低位 $1$ 所在的位数，而是这个 $1$ 与它后面所有 $0$ 组成的数，即 $2^k$

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

对一个单点进行修改操作，那么就需要修改它的所有父节点

例如修改上图的 $a_5$，则需要爬链修改 $s_5,s_6,s_8$

void change(int x,int k){
    while (x<=n){
        s+=k;//累加计算区间总值
        x+=lowbit(x);//向上传递父节点
    }
}

区间查询时，我们查询到的值为前 $x$ 个元素的前缀和

例如查询 $a_7$ ，爬链查询到的值为 $s_7+s_6+s_4$

int query(int x){
    int t=0;
    while (x){
        t+=s;//累加区间总值
        x-=lowbit(x);//爬链
    }
    return t;
}

输出区间和：

cin>>n>>m;
for (int i=1;i<=n;i++) cin>>a[i];//读入原数组

void build(void){
    for (int i=1;i<=n;i++){
        change(i,a[i]);
    }
}//初始化前缀和

int x,k;
cin>>x>>k;
change(x,k);//点修

int x,y;
cin>>x>>y;
cout<<query(y)-query(x-1)<<endl;//区查

利用两端的前缀和相减计算区间和

上面的操作利用前缀和，进行点修与区查功能，反之，也可以利用差分，进行区修与点查功能

设差分 $d_i=a_i-a_{i-1}$

$$ \implies \sum_{j=1}^id_j=a_i $$

所以

$$ a_{[x,y]}+k\iff d_{x}+k,d_{y+1}-k\\ \impliedby \sum_{j=1}^x d_j=a_x+k,\sum_{j=1}^yd_j=a_y+(x-y+1)*k,\sum_{j=1}^{y+1}d_j=a_{y+1}+(x-y+1)*k $$

int x,y,k;
cin>>x>>y>>k;
change(x,k);
change(y+1,-k);//区修
//树状数组中维护的差分信息

int x;
cin>>x;
cout<<a+query(x)<<endl;//点查
//查询到的值为树状数组的前缀和，差分+前缀和即为修改的值

下面考虑树状数组实现区修与区查，综合差分与前缀和

区间查询的推导公式，需要查询 $[1,r] $ 的区间和，使用差分构造等式

$$ \sum_{i=1}^r a_i=d_1+(d_1+d_2)+(d_1+d_2+d_3)+\cdots+\sum_{i=1}^r d_i $$

整理右式为

$$ =d_1*r+d_2*(r-1)+\cdots+d_{r-1}*2+d_r*1\\ =(\sum_{i=1}^rd_r)*r-(d_1*0+d_2*1+d_3*2+\cdots+d_r*(r-1)) $$

可以分成两个部分求值，通过构造两个树状数组维护查询前缀和 $s_1$ 维护 $d_i$ ，$s_2$ 维护 $d_i*(i-1)$

int n,m;
long long a[100010];
long long s1[100010],s2[100010];

void change(long long s[],long long x,long long k){
    while (x<=n){
        s+=k;
        x+=lowbit(x);
    }
    return;
}

long long query(long long s[],long long x){
    long long t=0;
    while (x){
        t+=s;
        x-=lowbit(x);
    }
    return t;
}

那么查询 $[x,y]$ 的区间和可以转化为

$$ [query(s_1,y)*y-query(s_2,y)]-[query(s_1,x-1)*(x-1)-query(s_2,x-1)] $$

long long x,y,k;
cin>>x>>y>>k;
change(s1,x,k);
change(s1,y+1,-k);//维护s1
change(s2,x,k*(x-1));
change(s2,y+1,-k*(y+1-1));//维护s2

输出区间和时因为处理原数组的方式不同，所以方法存在两种

• 显式处理前缀和

long long pre[100010];

for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];

int x,y;
cin>>x>>y;
long long sum=query(s1,y)*y-query(s2,y)-query(s1,x-1)*(x-1)+query(s2,x-1)+pre[y]-pre[x-1];
cout<<sum<<endl;    

这里的 $s_1,s_2$ 只是单纯地存储了差分的信息

• 隐式处理前缀和

for (int i=1;i<=n;i++) cin>>a[i];
build();

void build(void){
    for (int i=1;i<=n;i++){
        change(s1,i,a[i]);
        change(s1,i+1,-a[i]);
        change(s2,i,a[i]*(i-1));
        change(s2,i+1,-a[i]*(i+1-1));
    }
}

int x,y;
cin>>x>>y;
long long sum=query(s1,y)*y-query(s2,y)-query(s1,x-1)*(x-1)+query(s2,x-1);
cout<<sum<<endl;

这里将初始数组转换为树状数组的差分形式，相当于第一段代码中显式维护的前缀和数组

即 query(s1, y)*y - query(s2, y) 等价于前缀和 pre[y]