[总结] 树状数组

- 导语 -

　树状数组学得很渣， 只做了4道模板题, 但是一般也不会有树状数组的裸题做吧2333.
　学习的话, 大概可以看一下这篇.
　不过我学得很懵, 大概是半懂半记的样子.
　

- 单点修改&区间查询 -

　这里是题目.
　大概是树状数组的本职工作的样子...
　逆序对的话就是先设原数组为a, 把出现过的数从小到大排好序记录数组b, 以及记录数字出现个数的树状数组sum, 然后将数组a的数字依次插入数组b(单点修改), 插入时插入的位置前存在的数字数量便是以该数为右端可以构成的逆序对数目(区间查询), 总和就是答案.
　

- 区间修改&单点查询 -

　这里是题目.
　维护一个差分数组b. (b_i) = (a_i) - (a_{i-1}) (默认(a_0) = 0). 于是对于修改区间[x, y], 差分数组就只有(b_x) = (a_x) - (a_{x-1}) 和 (b_{y+1}) = (b_{y+1}) - (b_y) 是要变的, 完成了单点修改. 查询时(a_i) = (b_i) + (b_{i-1}) + ... + (b_1), 这样时间复杂度还是O(n)的, 我们考虑对 b 设一个树状数组 c, 那么查询 (a_i) 就只要O(log(n))的时间了, 但原本O(1)的修改也需要O(log(n))的时间, 注意此时b数组已经没用了, 所以实际上需要处理的只有c数组.
　

- 区间修改&区间查询 -

　这里是题目.
　还是记原数组为a, 差分数组为b.
　有:
　
　(a[n] = sum_{i=1}^n b_i)
　　
　于是求前缀和时即有:
　
　$sum_{i=1}^n a_i　=　sum_{i=1}^nsum_{j=1}i b_j　=　sum_{i=1}^n (n - i + 1) * b_i　＝　(n + 1) * sum_{i=1}^n b_i - sum_{i=1}^n i * b_i $
　
　于是我们对数组 (b_i) , (b_i * i) 各维护一个树状数组就能解决问题了.
　

- 维护区间最大值 -

　这里是题目．
　先看这张piao度娘的图片.

　记原数组为a, 记录最大值的数组为c.
　c数组和sum数组维护的区间是一样的, 故更新(c_i)时需用到(a_i), (c_{i-2^0}), (c_{i-2^1})...(c_{i-2^k}), (2^i < lowbit(i), 0 <= i <= k), 看到上图, 即更新一个段的最大值需要它正下方的所有段(区间[i-lowbit(i)+1, i-1])和(a_i), 如更新(c_8) = max((a_8), $c_{8-2^0}=c_7 $, $c_{8-2^1}=c_6 $, (c_{8-2^2}=c_4)).
　那么更新时有:

void update(int r) {
　c[r]=a[r];
　for(int i=1; i<lowbit(r); i<<=1)
　c[r]=max(c[r], c[r-i]);
}

　查询的话也是查找所有在区间内的段, 我们考虑对从右端开始的每一个i, 它的i-lowbit(i)是否在区间内, 在的话我们可以直接比较这个段并重复该步骤, 否则这个段就不能用来比较, 而要将当前位置上的数直接取出来比较, 然后继续向左重复上述步骤:
　(看到上图, 以区间[4, 7]为例, 先比较(a_7), 指针移到 6 , 由于 6-lowbit(6) = 4 >= 2, 故比较 (c_6) , 指针移到4, 由于 4-lowbit(4) = 0 < 4, 故不能考虑(c_4), 结束本次查询, 下次查询从(a_4)开始, 结束后指针移到3, 4 > 3, 查询结束.)

int get(int l, int r) {
    int tmp = a[r];
    while (l <= r) {
        tmp = Max(tmp, a[r]);
        for (--r; r - lowbit(r) >= l; r -= lowbit(r))
            tmp = Max(tmp, c[r]);
    }
    return tmp;
}

　我们发现, 更新时需要比较(a_i)与区间[i-lowbit(i)+1, i-1]的最大值(上文有提到),而这个问题恰好可以被get函数解决, 也就是说:

c[i] = max(get(i - lowbit(i) + 1, i - 1), a[i])

　这样就只要用一个函数来解决问题啦．