树状数组

发表于 更新于 分类于 阅读次数： Changyan：

树状数组

简记
1.快速求前缀和 O(logn)

2.修改某一个数 O(logn)

基于二进制的想法

对于一个序列 a[1]~a[n],树状数组用于维护其前缀和。支持logn复杂度求前缀和与logn复杂度修改序列中的某一个元素。

设我们有一个长度为n的序列，其中:

我们将此序列按照二进制的思想可以分成k段（k=n二进制表示下1的个数）：

如图，为tree[]为每一段绿色区间之和：

图中任意一个区间都能由之前若干个区间覆盖，而且覆盖区间的数量正好是当前区间二进制表示下1的个数，而且每次都递减最后一位1。因此我们可以借助lowbit运算来求得每一个构成的子区间：

1
2
3
int lowbit(int x){
    return x&-x;
}

建树方式：

在已知数组a[]的情况下有三种建树方式：
1.最简单的O(nlogn)
1
2
3
4
for(int i=1;i<=n;i++){
    int b=a[i]-a[i-1];
    add(i,b);
}
2.O(n)建树法：
1
2
3
4
5
for(int i=1;i<=n;i++){
    tree[i]=a[i]-a[i-1];
    for(int j=i-1;j>i-lowbit(i);j-=lowbit(j))
        tree[i]+=tree[j];
}
3.回归本质建树法O(kn)
1
2
3
//1.先预处理a[i]的前缀和
for(int i=1;i<=n;i++) a[i]+=a[i-1]
for(itn i=1;i<=n;i++) tree[i]=a[i]-a[i=lowbit(i)]

查询操作：

以c[16]为例：

因此我们可以总结出查询操作的模板：

1
2
3
4
5
6
int ask(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=tree[i];
    return res;
}

修改操作

我们逆向查询操作的步骤，当修改某一个数的值的时候，会逆向影响到由此数组成的所有查询路线，因此当修改一个值后，此数的所有查询路线对应的数都需要修改：

1
2
3
4
int add(int x,int c){ //在x位置插入c
    for(int i=x;i<=n;i+=lowbit(i))
        tree[i]+=c;
}
大致题型：

适用于针对一个区间的修改或者查询操作