树状数组

2023-08-06

树状数组，也称为二进制索引树，是一种支持单点更新和区间查询的数据结构。在大多数情况下，我们可以用它来查询区间和、区间乘积或其他满足以下条件的操作：

结合律：
具有逆运算，我们可以通过和推断出

它基于这样一个假设：任何前缀都可以分解为最多个区间，这些区间的信息是已知的。

从上图可以看出，每个位置控制的区间的右边界是。在树状数组中，被分配控制长度为的区间。这里，是从右边数第一个 1 位的位置减 1。例如，$12 = (1100)2 $，则$ k = 2 $，$ 2^k = 4 $。所以在这种情况下，$ c{12} $控制的区间是$ [12 - 4 + 1, 12] $。$ 2^k $可以使用函数获得，即$ x\ & \ (-x)$。

int lowbit(int x) {
    return x & (-x);
}
// 单点更新
void updateFT(int[] ft, int index, int val) {
    int diff = val - ft[index];
    while(index <= ft.length - 1) {
        ft[index] += diff;
        index += lowbit(index);
    }
}

void createFT(int[] arr) {
    int n = arr.length;
    int[] ft = new int[n + 1];
    for(int i=1;i<=n;i++) {
        updateFT(ft, i, arr[i-1]);
    }
}

void getSum(int[] ft, int end) {
    int ret = 0;
    while(end > 0) {
        ret += ft[end];
        end -= lowbit(end);
    }
    return ret;
}