Fenwick tree or BIT

Overview

*定义树状数组为,

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

它所解决的典型问题如下.

Typical problem

给定一个整数数组a[1~n], 求区间[i,j]的和. 此外, 有时还会要求更新某个a[k]的值.

Key operations

树状数组的存储结构为数组t[1~n], 定义了3种基本操作, 如下所示.

int a[n + 1], t[n + 1]; // a表示输入数据; t为树状数组的存储结构
int lowbit(int i); // 两个用途: i += lowbit(i)为其父结点; t[i] = sum[i - lowbit(i) + 1, i]
void update(int i, int k); // 若现在要求更新a[i]的值，即a[i] += k，update就更新数组t
int getsum(int i); // 求区间a[1...i]的值

其中, getsum(i)可以在 O ( log ⁡ ( n ) ) O(\log(n)) O(log(n))的时间复杂度内求出区间[1,i]的值. 显然, 区间[i,j]的值就可以用如下的公式求出.
sum ( i , j ) = getsum ( j ) − getsum ( i − 1 ) . \text{sum}(i,j)=\text{getsum}(j) - \text{getsum}(i-1). sum(i,j)=getsum(j)−getsum(i−1).

Data Structure

Structure in Picture

树状数组的结构如下图所示.

定义操作lowbit(i)如下,

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

那么便有,
t [ i ] = ∑ j = i − lowbit ( i ) + 1 i a [ j ] . t[i]=\sum_{j=i-\text{lowbit}(i) + 1}^{i}a[j]. t[i]=j=i−lowbit(i)+1∑i​a[j].
而结点i的父结点为,
i + = lowbit(i) . i += \text{lowbit(i)}. i+=lowbit(i).
例如,

• i = 1, 00000001 & (-1: 11111111) = 1; 父结点为2 = 1 + 1; t[1] = a[1], 表示区间[1, 1]的和
• i = 2, 00000010 & (-2: 11111110) = 2; 父结点为4 = 2 + 2; t[2] = a[1] + a[2] = t[1] + a[2], 表示区间[1, 2]的和
• i = 3, 00000011 & (-3: 11111101) = 1; 父结点为4 = 3 + 1; t[3] = a[3], 表示区间[3, 3]的和
• i = 4, 00000100 & (-4: 11111100) = 4; 父结点为8 = 4 + 4; t[4] = a[1] + a[2] + a[3] + a[4] = t[2] + t[3] + a[4], 表示区间[1, 4]的和

Code

实现具体代码如下

int a[n + 1], t[n + 1]; // a表示输入数据; t为树状数组的存储结构

// 两个用途: i += lowbit(i)为其父结点; t[i] = sum[i - lowbit(i) + 1, i]
int lowbit(int i) { 
    return i & -i;
}

// 若现在要求更新a[i]的值，即a[i] += k，update就更新相应的数组t
void update(int i, int k) { 
    while (i <= n) { // 从当前结点依次向上更新
        t[i] += k;
        i += lowbit(i);
    }
}

// 求区间a[1...i]的值
int getsum(int i) { 
    int sum = 0;
    while (i >= 1) { // 依次向下求
        sum += t[i];
        i -= lowbit(i);
    }
    return sum;
}

• getsum(i)的时间复杂度为 O ( log ⁡ ( n ) ) O(\log(n)) O(log(n))
• update(i)的时间复杂度为 O ( log ⁡ ( n ) ) O(\log(n)) O(log(n))

Examples

• PAT(Advanced Level) 1057 Stack
  • addr: https://pintia.cn/problem-sets/994805342720868352/problems/994805417945710592