树状数组 Fenwick Tree / Binary Index Tree

树状数组 Fenwick Tree / Binary Index Tree

基本数据结构

树状数组类似线段树，但实现代码更短一些（但有一些同学认为比线段树更难理解），可以支持方便的单点/欧战修改和单点/区域查询操作。

树状数组和线段树可以选择掌握，大部分题目两者都可以用（线段树更通用一些），一般来说两种方法保证掌握一个就可以了。

如上图示，定义 c[]c[] 树状数组，来跟踪 a[]a[] 的信息，使得在aa上面做的查询，可以在cc上更快的完成。比如c2c_2管理a1,a2a_1,a_2。 可以看到节点覆盖的求和范围是有重叠的，所以做单点修改时，需要改动多个节点。

定义一个lowbit函数，用来帮助我们定位cc数组的下标：

// 返回二进制表示中最低的位：lowbit(0b10110000) == 0b00010000
// 这个计算方法来自补码：“取反加一”
int lowbit(int x) {return x & -x;}

树上的两个基本操作就是add()和getsum():

void add(int x, int k) {
  while (x <= n) {  // 不能越界
    c[x] = c[x] + k;
    x = x + lowbit(x);
  }
}
int getsum(int x) {  // a[1]..a[x]的和
  int ans = 0;
  while (x >= 1) {
    ans = ans + c[x];
    x = x - lowbit(x);
  }
  return ans;
}

单点修改，区间求和

用上面图中所示的标准定义的树状数组，就已经可以解决单点修改、区间求和的问题。

对照上面图中的数组范围，可以验证以上算法的正确性。

模板例题是LibreOJ 130: 树状数组模板题（单点修改，区间查询）

参考代码:

#include <iostream>
#include <cstring>
using namespace std;
 
long long bit[1000010];
int n, q, act, l, r;
 
// x 的二进制表示中，最低位的 1 的位置。
// lowbit(0b10110000) == 0b00010000
// lowbit(0b11100100) == 0b00000100
// 这个计算方法来自补码：“取反加一”
int lowbit(int x) { return x & (-x); }
 
void update(int x, int k) {
    while (x <= n) {
        bit[x] += (long long)k;
        x += lowbit(x);
    }
}
 
long long getSum(int x) {
    long long ans = 0;
    while (x > 0) {
        ans += bit[x];
        x -= lowbit(x);
    }
    return ans;
}
 
int main() {
    while (cin >> n >> q) {
        memset(bit, 0, sizeof(bit));
        for (int i = 1, x; i <= n; ++i) {
            cin >> x;
            update(i, x);
        }
        while (q--) {
            cin >> act >> l >> r;
            if (act == 2) {
                cout << getSum(r) - getSum(l - 1) << endl;
            } else {
                update(l, r);
            }
        }
    }
    return 0;
}

区间修改、单点查询

如果我们的问题是区间修改的，那么我们可以把aa定义成目标数组的差分值，这样就能把区间修改转化为起点、终点的差分值的单点修改，把单点查询转化为1到此点的区间查询操作。

例如LibreOJ 131: 区间修改、单点查询

参考代码:

    #include<stdio.h>
    #define ll long long 
    ll c[1000010];
    ll n,q;
    ll lowbit(ll x)
    {
        return x&(-x);
    }
    void add(ll i,ll a)
    {
        while(i<=n)
        {
            c[i]=c[i]+a;
            i=i+lowbit(i);
        }
    }
    ll sum(ll x)
    {
        ll ans=0;
        while(x>0)
        {
            ans=ans+c[x];
            x=x-lowbit(x);
        }
        return ans;
    }
    int main()
    {
        ll i,a,b=0;
        scanf("%lld %lld",&n,&q);
        for(i=1; i<=n; i++)
        {
            scanf("%lld",&a);
            add(i,a-b);
            b=a;
        }
        while(q--)
        {
            ll s,l,r,x;
            scanf("%lld",&s);
            if(s==1)
            {
                scanf("%lld %lld %lld",&l,&r,&x);
                add(l,x);
                add(r+1,-x);
            }
            else if(s==2)
            {
                int h;
                scanf("%lld",&h);
                printf("%lld\n",sum(h));
            }
        }
    }

区间修改、区间查询

再进一步，如果需要在区间修改的数组上做区间查询，那么我们还是维护差分值作为数组，但这时区间查询就变得更复杂一些。

若维护序列 aa 的差分数组 bb，此时我们对 aa 的一个前缀 rr 求和，即 ∑i=1rai\sum_{i=1}^{r} a_i，由差分数组定义得 ai=∑j=1ibja_i=\sum_{j=1}^i b_j

进行推导

∑i=1rai=∑i=1r∑j=1ibj=∑i=1r[bi×(r−i+1)]=(r+1)∑i=1rbi−∑i=1r(ibi)\begin{aligned} &\sum_{i=1}^{r} a_i \\ =&\sum_{i=1}^r\sum_{j=1}^i b_j \\ =&\sum_{i=1}^r [b_i\times(r-i+1)] \\ =&(r+1) \sum_{i=1}^r b_i - \sum_{i=1}^r (i b_i) \end{aligned}

我们用两个树状数组分别维护 ∑bi\sum b_i 和 ∑(ibi)\sum (i b_i)，就能实现区间求和。如下图所示：

例题LibreOJ 132：区间修改、区间查询 参考代码:

    int t1[MAXN], t2[MAXN], n;
 
    inline int lowbit(int x) { return x & (-x); }
 
    void add(int k, int v) {
        int v1 = k * v;
        while (k <= n) {
            t1[k] += v, t2[k] += v1;
            k += lowbit(k);
        }
    }
 
    int getsum(int *t, int k) {
        int ret = 0;
        while (k) {
            ret += t[k];
            k -= lowbit(k);
        }
        return ret;
    }
 
    void add1(int l, int r, int v) {
        add(l, v), add(r + 1, -v);  // 将区间加差分为两个前缀加
    }
 
    long long getsum1(int l, int r) {
        return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
                (getsum(t2, r) - getsum(t2, l - 1));
    }

习题

习题
P3374【模板】树状数组 1普及/提高-
P3368【模板】树状数组 2普及/提高-
P2357守墓人普及/提高-
P6278USACO GoldHaircut2020普及+/提高
P4868Preprefix sum普及+/提高
P1637三元上升子序列普及+/提高
P3253JLOI删除物品2013提高+/省选-
P4085USACO GoldHaybale Feast2017提高+/省选-
P1972SDOIHH的项链2009提高+/省选-
P6186NOI Online冒泡排序提高+/省选-
P4145上帝造题的七分钟 2 / 花神游历各国提高+/省选-
CF703DCFMishka and Interesting sum省选/NOI-