树状数组 - HOXIANSEN's Blog

树状数组介绍

树状数组是简化版的线段树（实现起来更简单），用于对一个数组进行快速的单点修改和区间查询。它可以在O(logN)的时间复杂度内完成单点修改、区间查询等操作，相较于线段树等其他数据结构，树状数组实现起来比较简单。

树状数组将原数组转化为一颗多叉树，每个节点存储的是一段连续区间的信息。每个节点的值都是其子节点值的合并结果，从而实现快速区间查询的目的。

如何计算一个非负整数n的二进制最低位的1及其后面的0构成的数？
例如：44=(101100)₂，lowbit(44)=lowbit(((101100)₂))=(100)₂=4

我们可以对44按位取反再加1，即~44+1，得到-44。然后再把-44和44按位与运算，得到结果。

所以 lowbit(n) = n & (-n)

在构建数组时，当前节点的父节点的索引值的计算方式是：index_parent=index_child+lowbit(index_child)，父节点的值为其子节点的值的和（前缀和）。

在单点修改时，除了更新当前节点外，还需要递归更新父节点，代码如下：

void add(int i, int x) {
    do {
        tree[i] += x;
        // 找父节点
        i += lowbit(i);
    } while(i < tree.length);
}

假设需要求prefix[7]，从上图可以看出，prefix[7]=tree[7]+tree[6]+tree[4]，进一步发现，6=7-lowbit(7)，4=6-lowbit(6)。即逐次减去二进制最后面那个1。

代码如下：

int prefix(int i) {
    int sum = 0;
    do{
        sum += tree[i];
        i -= lowbit[i];
    } while(i > 0);
    return sum;
}

要查询区间和，将前缀和相减可以得到。具体看代码：

int search(int l, int r) {
    // 这里是求左闭右闭区间[l,r]
    return prefix(r) - prefix(l - 1);
}