Skip to content

树状数组 Fenwick Tree / Binary Index Tree

基本数据结构

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

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

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

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

// 返回二进制表示中最低的位：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;
}

区间修改、单点查询

如果我们的问题是区间修改的，那么我们可以把\(a\)定义成目标数组的差分值，这样就能把区间修改转化为起点、终点的差分值的单点修改，把单点查询转化为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));
        }
    }
}

区间修改、区间查询

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

若维护序列 \(a\) 的差分数组 \(b\)，此时我们对 \(a\) 的一个前缀 \(r\) 求和，即 \(\sum_{i=1}^{r} a_i\)，由差分数组定义得 \(a_i=\sum_{j=1}^i b_j\)

进行推导

\[ \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} \]

我们用两个树状数组分别维护 \(\sum b_i\) 和 \(\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));
}

习题