树状数组

介绍

树状数组多用于单点修改和区间查询，是一种代码量小的数据结构，扩展数据结构为线段树。

图示

最下面的八个方块代表原始数据数组 a。上面参差不齐的方块（与最上面的八个方块是同一个数组）代表数组 a 的上级——c 数组，即树状数组结构。
c 数组就是用来储存原始数组 a 某段区间的和的，也就是说，这些区间的信息是已知的，我们的目标就是把查询前缀拆成这些小区间。
例如，从图中可以看出：

$c_2$ 管辖的是 $a[1 \ldots 2]$；

$c_4$ 管辖的是 $a[1 \ldots 4]$；

$c_6$ 管辖的是 $a[5 \ldots 6]$；

$c_8$ 管辖的是 $a[1 \ldots 8]$；

剩下的 c[x] 管辖的都是 a[x] 自己（可以看做 $a[x \ldots x]$ 的长度为 1 的小区间）。

lowbit函数

例如，欲查询 a 数组第1元素到第7元素的和，可以分解为$c_4+c_6+c_7$，即从 $c_7$ 开始依次向左跳跃。

跳跃的节点依据 lowbit 函数：

int lowbit(int x) {
  // x 的二进制中，最低位的 1 以及后面所有 0 组成的数。
  // lowbit(0b01011000) == 0b00001000
  //          ~~~~^~~~
  // lowbit(0b01110010) == 0b00000010
  //          ~~~~~~^~
  return x & -x;
}

lowbit函数可以提取节点序号最低位的1，
观察到每次将节点序号最低位1置0，就是下一跳位置，因此可以不断将查询节点进行lowbit直到下一跳为0。

而查询任意区间和只需将左右序号查询结果相减。

int Query(int pos1,int pos2) {
    int ret1, ret2 = 0;
    while (pos2 > 0) {
        ret2 += c[pos2];
        pos2 -= LowBit(pos2);
    }
    while (pos1 > 0) {
        ret1 += c[pos1];
        pos1 -= LowBit(pos1);
    }
    return ret2-ret1;
}

而在对线段数组进行更新时，只需按照查询方法在每一跳的树状数组节点上进行更新。

---

算法示例

    class SegmentTree{
	private:
		
		std::vector<int> c;
		inline int LowBit(int x){
			return x&(-x);
		} 
		
	public:
		
	    SegmentTree(int length) {
	        c.resize(length, 0);
	    }

		// pos1->pos2加上i
	    void Update(int pos1, int pos2, int i) {
	        while (pos1 < c.size()&&pos1 <= pos2) {
	            c[pos1] += i;
	            pos1 += LowBit(pos1);
	        }
	    }
	
		// 求pos1->pos2总和
	    int Query(int pos1,int pos2) {
	        int ret1, ret2 = 0;
	        while (pos2 > 0) {
	            ret2 += c[pos2];
	            pos2 -= LowBit(pos2);
	        }
	        while (pos1 > 0) {
	            ret1 += c[pos1];
	            pos1 -= LowBit(pos1);
			}
	        return ret2-ret1;
	    }
	
};

---

算法分析

1. 时间复杂度 $O(\log n)$
2. 空间复杂度 $O(n)$

---

例题

1. leetcode 218.天际线问题
2. leetcode 307.区域和检索 - 数组可修改