树状数组-入门

Basic Concept

树状数组可以用于高效计算数列的前缀和，区间和等等。

它可以支持在$O(logn)$的时间内得到任意前缀和，以及在$O(logn)$时间内支持对区间单点值的修改。空间复杂度为$O(n)$。

数组存储方式

如图所示。

$A[i]$代表原数组的元素，$C[i]$代表树状数组中的元素。

C[1]=A[1];
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

而其索引的二进制表示如下：

C[1] = C[0001] = A[1];
C[2] = C[0010] = A[1]+A[2];
C[3] = C[0011] = A[3];
C[4] = C[0100] = A[1]+A[2]+A[3]+A[4];
C[5] = C[0101] = A[5];
C[6] = C[0110] = A[5]+A[6];
C[7] = C[0111] = A[7];
C[8] = C[1000] = A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

我们可以找出规律，

$C[i] =\sum_{k=把i二进制表示的最低位1置为0后，将新的值+1}^i A[k]$

也就是说，问题在于如何找出$i$的最低位$1$所代表的数值。

lowbit

这里我们可以引入lowbit函数。

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

我们已经知道，对于整数表示，有

正数的补码是其本身；
负数的补码是在反码的基础上$+1$；

因此x & (-x)就可以满足我们对于查找最低位$1$的需求。

举个例子：

二进制数 $11010$ (1)
其反码为 $00101$ (2)
加 $1$ 后为 $00110$ (3)
将(1)(3)两者相与便得到最低位的 $1$ 所表示的数值

树状数组的建立

上面准备工作都做好了，码就行了:(

#include <iostream>
#define MAXN 12
using namespace std;

int ft[MAXN+1] = {0};
int a[MAXN + 1] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

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

void generateTree(){
    for (int i = 1; i <= MAXN; i++){
        for (int k = i - lowbit(i) + 1; k <= i; k++)
            ft[i] += a[k];
    }
}

int main(){
    generateTree();
    return 0;
}

单点更新

再把这张图拿过来：

如果我们要更改$A[3]$的值，那么我们知道，$C[3], C[4], C[8]$ 的值都会受到影响。

$3(011)$ => C[3] += temp;
$lowbit(3) = 001$, $3 + lowbit(3)= 100 = 4(100)$ => C[4] += temp;
$lowbit(4) = 100$, $4+lowbit(4)=1000=8(1000)$ => C[8] += temp;
……

因此，我们只需要对所要更新的数据不断使其自增lowbit后，

使树状数组的对应索引增加 temp 值即可。

void update(int index, int val){
    for (int i = index; i <= MAXN; i = i + lowbit(i)){
        ft[i] += val;
    }
}

区间查询

假设现在我们要查询1~7的前缀和。

C[7] = C[0111] = A[7];
C[6] = C[0110] = A[5] + A[6];
C[4] = C[0100] = A[1] + A[2] + A[3] + A[4];

归纳可知，我们只需每次将索引减少i的lowbit，然后将对应的树状数组的值求和即可。

int getSum(int index){
    int result = 0;
    for (int k = index; k > 0; k-=lowbit(k)){
        result += ft[k];
    }
    return result;
}