树状数组

树状数组代替线段树。 —— zzz《常数优化与 NOILinux》

顾名思义，树状数组是一种树形结构，但是因为他独特的结构和拆分方式（二进制你又来了是吧），可以直接用数组存储。
用途是解决大部分区间修改查询问题，复杂度一般是 \(\operatorname{O}(\log n)\) ，同时常数小（暗示 线段树 不行），同时码量小，好理解（暗示 * 2），但是复杂的区间修改查询问题不能解决，同时区间最大最小值也不能用它处理（后文会说）

Update on 2023/6/7 本质上就是能够以极小的常数且严格 \(\operatorname{O}(\log n)\) 的时间复杂度进行单点修改与前缀和的维护，不过这个前缀和可以玩得比较花。

实际上原理看看就得了，这玩意板子写完了半年过去都不带忘的...

关于常数差距到底多大？S2 的同学们可以看看 S2OJ # 786，使用普通快读仅 2.60s（现在最快的我的提交记录是卡常版的），线段树解法貌似最快的是 lyq 学长的 6.69s。

基本树状数组

原理

来自学长的一张图
注意下文基本上所有东西都可以/需要搭配这个图进行理解

以求区间和的树状数组为例，树中每一个节点存储一段区间的和，询问时进行前缀和加减即可得出任意区间的和。
分区间的方法即利用二进制，对于第 \(i\) 节点来说，\(i\) 的二进制形式中最低一位 1 的位置为 \(x\)，那么 \(tree_i\) 就存储了 \([i-2^x+1,i]\) 区间的和。
注意此处 \(x\) 从 0 开始算
以 \(3\) 为例，\(3\) 的二进制为 0000 0011，最低一位 1 的位置是 0，则 \(tree_3\) 存储 \([3-1+1,3]\) 即 \([3,3]\) 的区间和。
再以 \(8\) 为例，\(8\) 的二进制为 0000 1000，最低一位 1 的位置是 3，则 \(tree_8\) 存储 \([8-8+1,8]\) 即 \([1,8]\) 的区间和。

实现

建立

实际上不用特意处理建立，直接在输入过程中每输入一个数就修改即可。

1
2
3
4

for (int i = 1; i <= n; ++i) {
    cin >> t1; // tmp
    modify(i,t1);
}

lowbit

本函数实现查找一个数最后一位 \(1\) 的位置。

首先声明一个冷知识（大概冷），位运算是针对内存中存储的原数据的运算，换句话说，进行位运算的是补码而不是原码。

原码即一个数本身的二进制表示，反码即在原码的基础上符号位不变其他位取反。
补码分类来说，正数的补码是它的原码，负数的补码为其反码\(+1\)。

在这里我们只考虑最后一位 1 及它后面的 0。
比如 0011 0100 这个二进制数，我们先把它变成负数，即按位取反后加一（易证这就是他的相反数），变为 11001011 再变为 11001100。
发现了一件神奇的事情，原来最低一位 1 竟然回来了！
显然，这位 1 前面的所有数字因为被取反所以和原数完全不同；后面的所有数字原来一定是 0 取反后变成一排 1，负数的补码是反码\(+1\)，从而一直进位到原来最后一位 1 这里，而它们本身变回了 0 ；又因为这位 1 被取反后是 0 所以无论如何都不会再向前进位。
从而保证对于任意一个正数 \(x\)，\(-x\) 与 \(x\) 的存储只有 \(x\) 本身最后一位 1 是相同的。
因此 lowbit() 的实现就非常简单了，直接用 x&-x，得到的结果就是原理中所说的 \(2^x\)，又快又好想，用着还方便。

1
2
3

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

单点修改

假设修改为给第 \(x\) 个数增加 \(v\)，那我们就需要修改所有包含第 \(x\) 个元素的节点，则从第 \(x\) 个节点寻找父亲节点直到根节点为止（参考上图）。
\(x\) 节点的直接父亲是 \(x+\operatorname{lowbit}(x)\)，因此直接一层循环实现 \(\operatorname{O}(\log n)\) 修改。

1
2
3
4
5

void modify(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += v;
    }
}

区间查询

查询区间为 \([l,r]\) 时，将问题转化为求 \([1,r] - [1,l-1]\) 的值（前缀和知识），因此我们只需要实现查询前缀和的功能即可。
因为 \(i\) 节点存储的是一段长度为 \(\operatorname{lowbit}(i)\) 的区间的和，因此取完 \(i\) 号点的值后再取 \(i-\operatorname{lowbit}(i)\) 号节点的值，直到位置变为 \(0\)（到头）即可（看不懂就结合上面图）

1
2
3
4
5
6
7
8
9

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) {
        res += tree[i];
    }
    return res;
}

ans = query(r) - query(l-1);

改区间查单点

上文我们解决了求前缀和的问题，本次需要查询单点，那么很容易联想到差分。更改区间对应改差分数组上的两个点，查询单点对应查询差分数组的前缀和。

区间加区间求和

发现树状数组好快于是回来补一下（2023.6.23）

对原数组进行差分，易得：

\[ d_i = a_i - a_{i-1} \newline a_i = \sum_{j=1}^i d_i \newline \]

取 \([1,x]\) 的区间和，即为：

\[ \begin{aligned} ans &= \sum_{i=1}^x a_i \newline &= \sum_{i=1}^x\sum_{j=1}^{i} d_i \newline &= \sum_{i=1}^x d_i(x-i+1) \newline &= \sum_{i=1}^x(1+x)d_i-\sum_{i=1}^x i\cdot d_i \end{aligned} \]

第二行到第三行那里不知道怎么推出来的话，观察每个 \(d_i\) 出现的次数，显然 \(d_1\) 出现 \(x\) 次，\(d_2\) 出现 \(x-1\) 次（除了 \(i=1\) 的时候都出现了），于是轻松推出来。

因此我们只需要维护两个树状数组，一个维护 \(d_i\) 即差分数组，另一个维护 \(i\cdot d_i\) 即可。

注意：此处树状数组维护的仍然是前缀和，\(i\cdot d_i\) 中的 \(i\) 就是修改的位置，而不是树状数组修改时循环的 \(i\)。

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#define N 100005

i64 id[N], d[N];
i32 n;

inline void mod(i32 pos, i64 val) {
    for (i32 i = pos; i <= n; i += lowbit(i)) {
        id[i] += pos * val;
        d[i] += val;
    }
}

inline i64 que(i32 pos) {
    i64 res = 0;
    for (i32 i = pos; i; i -= lowbit(i)) {
        res += d[i] * (pos + 1) - id[i];
    }
    return res;
}

inline void modify(i32 l, i32 r, i64 val) {
    mod(l, val);
    mod(r + 1, -val);
}

inline i64 query(i32 l, i32 r) {
    return que(r) - que(l - 1);
}