树状数组

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

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

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

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

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

基本树状数组

原理

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

以求区间和的树状数组为例，树中每一个节点存储一段区间的和，询问时进行前缀和加减即可得出任意区间的和。
分区间的方法即利用二进制，对于第 𝑖 节点来说，𝑖 的二进制形式中最低一位 1 的位置为 𝑥，那么 𝑡⁢𝑟⁢𝑒⁢𝑒𝑖 就存储了 [𝑖 −2𝑥 +1,𝑖] 区间的和。
注意此处 𝑥 从 0 开始算
以 3 为例，3 的二进制为 0000 0011，最低一位 1 的位置是 0，则 𝑡⁢𝑟⁢𝑒⁢𝑒3 存储 [3 −1 +1,3] 即 [3,3] 的区间和。
再以 8 为例，8 的二进制为 0000 1000，最低一位 1 的位置是 3，则 𝑡⁢𝑟⁢𝑒⁢𝑒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 所以无论如何都不会再向前进位。
从而保证对于任意一个正数 𝑥，−𝑥 与 𝑥 的存储只有 𝑥 本身最后一位 1 是相同的。
因此 lowbit() 的实现就非常简单了，直接用 x&-x，得到的结果就是原理中所说的 2𝑥，又快又好想，用着还方便。

1
2
3

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

单点修改

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

1
2
3
4
5

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

区间查询

查询区间为 [𝑙,𝑟] 时，将问题转化为求 [1,𝑟] −[1,𝑙 −1] 的值（前缀和知识），因此我们只需要实现查询前缀和的功能即可。
因为 𝑖 节点存储的是一段长度为 lowbit⁡(𝑖) 的区间的和，因此取完 𝑖 号点的值后再取 𝑖 −lowbit⁡(𝑖) 号节点的值，直到位置变为 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）

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

𝑑𝑖=𝑎𝑖−𝑎𝑖−1𝑎𝑖=𝑖∑𝑗=1𝑑𝑖

取 [1,𝑥] 的区间和，即为：

𝑎⁢𝑛⁢𝑠=𝑥∑𝑖=1𝑎𝑖=𝑥∑𝑖=1𝑖∑𝑗=1𝑑𝑖=𝑥∑𝑖=1𝑑𝑖⁢(𝑥−𝑖+1)=𝑥∑𝑖=1(1+𝑥)⁢𝑑𝑖−𝑥∑𝑖=1𝑖⋅𝑑𝑖

第二行到第三行那里不知道怎么推出来的话，观察每个 𝑑𝑖 出现的次数，显然 𝑑1 出现 𝑥 次，𝑑2 出现 𝑥 −1 次（除了 𝑖 =1 的时候都出现了），于是轻松推出来。

因此我们只需要维护两个树状数组，一个维护 𝑑𝑖 即差分数组，另一个维护 𝑖 ⋅𝑑𝑖 即可。

注意：此处树状数组维护的仍然是前缀和，𝑖 ⋅𝑑𝑖 中的 𝑖 就是修改的位置，而不是树状数组修改时循环的 𝑖。

核心代码：

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);
}