树状数组

这道题的原型是洛谷 P3374，那道题只有前两条。这里多要了一行「整个数组的和」。

它看起来像凑数，其实是专门为一个 bug 准备的一条腿： 后面会证明，sum(r) 那条路只有在 r = n 时才碰得到 c[n] —— 而随机造一个 l ≤ r 出来，r 正好等于 n 的概率是 (1 + 1/2 + … + 1/n) / n ≈ ln n / n （n = 8 时还有 34%，n = 2×10⁵ 时只剩 0.006%）。 这一行是唯一保证 r = n 的那次查询。

⚠ 这是第 35、36、37 章那条「题面多问一句，对拍就多一条腿」的第四次现场。 第 37 章给它划过一条边界（它是给数据不够狠的时候兜底的，不是万能药）， 这一章的账正好复刻了那条边界，而且这次能说清它兜的到底是什么：

★★ 弱数据上它把那个 bug 从 98 抬到 187（接近翻倍）， 数据够狠之后只值 263 → 280。 ★ 而它兜的正是「随机数据碰不到的那个边界」（r = n）—— 操作一多，随机查询里迟早会撞上 r = n，它的边际价值自然就掉下来了。

8 7
3 1 4 1 5 9 2 6

2 1 8      → 31        整个数组的和
1 3 5      →           a[3] = 4+5 = 9   ★ 这次修改要跑三格：c[3] → c[4] → c[8]
2 3 6      → 24        9+1+5+9
2 7 7      → 2         ★ sum(7) 要走三格（7 的二进制 111，三个 1）—— n=8 时最长的一条查询路
1 1 -3     →           a[1] = 0         ★ 这次修改要跑四格：c[1] → c[2] → c[4] → c[8]（最长）
1 8 -6     →           a[8] = 0         ★ 这次只跑一格（c[8] 就到头了）—— 最短
2 2 5      → 16        1+9+1+5

答案：31 24 2 16，最后一行 27。

• 第 4 条操作 2 7 7，是「查询路径最长」的现场（popcount(7) = 3）；
• 第 5、6 条那两次修改，一次跑四格一次跑一格 —— ★ 同一个 n，同一种操作，开销差四倍， 这件事第 9 步会变成一整张表；
• 而最后那个 27，是「add 循环写成 i < n」唯一的现场 —— ★ 那个 bug 的前四行输出一个字都不错。

⚠ 所以「这两个暴力哪个更慢」这个问题本身没有答案 —— 除非你先说清楚操作配比是多少。 这件事下一步就要量出来，而它决定了这一章的耗时表必须有两端。

秒表失灵，那就数次数（第 21 章 stairsCount.cpp 以来的老规矩：次数可复现，秒数不可复现）。

口径很简单：读或写数组里的一个元素，算碰一格。

点「运行 ▶」看结果

实测（./genBig 20000 20000 档位，n = m = 2×10⁴，全部写进了 check:viz）：

★★ 这张表比秒表诚实得多，而且它说的话有点反直觉：

树状数组在任何一端都不是最优的。 全查询时前缀和比它少七倍（4 万 vs 28.6 万），全修改时原数组比它少四倍（4 万 vs 15.3 万）。 ★ 它赢的地方是「两端都不烂」 —— 一半一半的时候，两个暴力一个 4991 万、一个 1.01 亿， 而它 21.9 万，少了两个数量级。

（第 37 章那句「堆赢在两列同时是 O(log n)」的加强版：那一章堆在两列上都不输， 这一章树状数组在每一端都输一点点，可它是唯一一个中间不崩的。）

⚠ 两张表的规模不一样，这是故意的，得说明白： 碰格数可复现，所以选了跑得起的规模并写成断言（n = m = 2×10⁴）； 耗时和机器有关，断言不了，所以要拧到足够大才看得出差别（n = m = 2×10⁵）。

lowbit(i) = i & -i —— i 的二进制里最低位的那个 1（连同它后面的 0）。

lowbit(6) = lowbit(0b110) = 0b10 = 2
lowbit(7) = lowbit(0b111) = 0b01 = 1
lowbit(8) = lowbit(0b1000) = 8

★ 定义：c[i] = a[i−lowbit(i)+1] + … + a[i]，也就是以 i 结尾、长度正好 lowbit(i) 的那一段。

对照一下就明白它到底改了什么：

攒得少，所以改一个数只会影响少数几格。

① 查前缀和 sum(r) = a[1] + … + a[r]

c[r] 已经管住了 (r−lowbit(r), r]，剩下的是 (0, r−lowbit(r)] —— 同一个问题，规模变小了（第 1、2 章那句「把大问题切成同形状的小问题」）。于是：

for (int i = r; i > 0; i -= lowbit(i)) s += c[i];

★ i -= lowbit(i) 干的事是「抹掉二进制里最低位的那个 1」， 所以循环转的圈数恰好等于 r 的二进制里 1 的个数（popcount）—— ⚠ 注意这不是「不超过」，是等号。它 ≤ ⌊log₂r⌋ + 1，于是 O(log n)。

sum(7) = c[7] + c[6] + c[4]      3 格，popcount(7) = 3   ← n=8 时最长
sum(8) = c[8]                    1 格，popcount(8) = 1   ← 一步到头

② 改 a[p] += x：所有管到 p 的格子都要跟着加 x。

for (int i = p; i <= n; i += lowbit(i)) c[i] += x;

★ i += lowbit(i) 干的事是「进位」：设 lowbit(i) = 2^k，那么 i 的第 k 位是 1， 加上 2^k 必然往上进位，第 k 位（连同它上面那串连续的 1）全变成 0 —— 所以新的 lowbit 严格比旧的大。最低位的 1 一路往高位挪，最多挪 ⌊log₂n⌋+1 次就超过 n 了。

add(1): c[1] → c[2] → c[4] → c[8]      4 格   ← 最长
add(8): c[8]                           1 格   ← 最短

⚠ 为什么「管到 p 的格子」正好是那条路？ 两句话：

• 每一步都合法：i' = i + lowbit(i)，因为 lowbit(i') > lowbit(i) 且 i' − lowbit(i') < i − lowbit(i) < p ≤ i < i'，所以 c[i'] 也管着 p；
• 一个都不漏：设 j 管着 p 且 j > i，那 j 的区间完整地盖住 i 所在的位置， 于是 j ≥ i' —— 因为这些区间要么互相套住、要么完全不相交，永远不会「半重叠」。 ★ 这条性质是整个 lowbit 结构的地基。

⇒ 改 O(log n)、查 O(log n)。两边同时是 log —— 这就是它比那两个暴力强的全部原因。

c[i] 管的那一段 = a[i] 加上「它下面挂着的几个子段」。 顺着 i 从小到大扫，先把 a[i] 放进 c[i]，再把 c[i] 整个交给它爸爸 i + lowbit(i)：

for (int i = 1; i <= n; i++) {
    c[i] += a[i];
    int f = i + lowbit(i);
    if (f <= n) c[f] += c[i];
}

一遍扫完就建好了。碰的格子数是 n（放进去）+ 有爸爸的格子数，而：

★★ 没有爸爸的格子（i + lowbit(i) > n），恰好就是 sum(n) 那条路上的格子。 所以建树碰的格子数 = 2n − popcount(n)，一个数都不多。

n = 2×10⁴ 时 popcount = 5，实测正好 39 995 = 40 000 − 5（check:viz 钉着这条）。

⚠ 对照一下「老老实实做 n 次 add」的写法：同样是 n = 2×10⁴，它要碰 153 456 格， 是 O(n) 建树的 3.84 倍。

点「运行 ▶」看结果

★ 注意 buildSlow.cpp 不是错误版本 —— 它 300 轮逐字节和正解相同。 对拍在它身上一个字都看不见，这一章后面还会碰到同样的事。

这是第 37 章立的规矩（写在 gen.cpp 开头）。这一章的清单是：

★★ 这一章冒出来一类前 37 章从没有过的旋钮：下标的二进制位形状。 以前的旋钮是值域 / 规模 / 结构角色 / 操作序列，说的都是「数据长什么样」； 这一次说的是「下标长什么样」—— 它和数值一点关系都没有。

• wrongEnd 只错最后那一行：因为 n = 8，每次 add 都要经过 c[8]（它漏掉了）， 而只有 sum(8) 才会去读 c[8] —— 也就是题面多问的那一行。
• wrongVar 只有最后那一行对：它每次减掉的是同一个 lowbit(r)， 而 r = 8 是 2 的幂，一步就减到 0，加的正好只有 c[8] —— 完全正确。

★★ 同一个事实（n = 8 是 2 的幂）同时是一个 bug 的死刑和另一个 bug 的赦免。 这就是下一步整张档位表的主线。

⚠ 还有一件事要单独说：wrongInt 在这组数据上一个字都不错。 它要的是「部分和超过 2³¹」，而这里最大的和才 31。

gen.cpp 带了十一个档位（./gen 种子 档位），种子固定 1..300：

★ 档位 0 那两个 0 是这一章的起点。「初始数组全 0」是我随手就写下来的 （「反正要什么值都能用操作加出来」）—— 可题面写的是 |a_i| ≤ 10⁹，0 只是其中一个值。

★ 第 27~34、37 章那条「生成器里那个不假思索的顺手写法，会悄悄给数据加一条题目里没有的性质」， 这一章第十次。这次加的那条性质是：「数组从空的开始」。 它一口气打掉了 wrongBuild（0 / 300），还顺手压住了 wrongRange（169，放开后 299）。

★★ 档位 2 和 3 是这一章真正的新东西，请对着看：

n 只取 2 的幂：wrongEnd 冲到 300 / 300（每次 add 都必经 c[n]）， 可 wrongVar 掉到 170（r = 2^k 时它是一份正确的程序）。 n 一个 2 的幂都不取：正好倒过来 —— wrongEnd 掉到 177，wrongVar 涨到 279。

★★ 同一个旋钮的两头，两个 bug 正好交换位置。 这是第 31 章那条「某一支永远走不到是坑，某一支占得太多也是坑」在这一章的样子， 而且形状比第 31 章那次干净得多：这里不是「多了挤掉别人」， 是一端直接把另一个 bug 变成了正确的代码。 ⇒ 所以档位 4 那样三种都造，才是唯一说得过去的选择。

① 值域拉开：单独加只值 28，放进最终环境是 0 → 207。 档位 6 单独加时 wrongInt 只有 28 / 300；档位 7 → 8 是 0 → 207。

★ 第 32、34、35、36、37 章那条「调优不可加」的第六次 —— 这次是正面的那一种：序列一长，部分和才真的堆得起来，值域拧满才有意义。

② ⚠ 而「n 的二进制形状」这一处，我差点做错。 第一版的混合档基数取到 16（也就是档位 10），在最终环境里量出来 wrongEnd = 251 —— 比什么都不改的对照档（272）还差。按第 34、35、37 章那条规矩，看着就该撤回。

可它同时改了两件事：形状（我想要的）和规模（顺手带上的，n 最大到 17）。 把规模那一半收回去（基数只到 8），同一处改动立刻变成 280 —— 反超对照档。

★★ 「量到主语」那条规矩（第 22、29、34、36 章）第一次用在生成器上： 一处改动量出来是负分时，先问它是不是偷偷夹带了第二个旋钮。

③ 最后定档：为什么留着「二进制形状」。 最终档（8）和对照档（9）的账很接近，而且一列涨一列跌： wrongEnd 280 vs 272（涨），wrongInt 207 vs 222（跌）。按「让最弱的那一支尽量强」的标准， 对照档反而略胜（222 > 207）。它还是被留下了，理由不是抓获率，是边界覆盖：

n = 2^k 时 c[n] 一格盖住整个数组，是这道题结构上最特殊的一支， 而顺手随机 [6,12] 里它只占 1/7。最终档 300 轮里有 91 轮 n 是 2 的幂。 ⚠ 这笔账要明写，不许粉饰成「改了就是更好」（第 27、35 章那条）。

第 11 章是「归并排序顺手数出来」（分治）。这一份换个角度：

从左往右扫，扫到 a[j] 时问一句：前面已经放进去的数里，有几个比它大？ 那些数下标更小、值更大 —— 每一个都是一个逆序对。

「前面放进去的数里有几个 ≤ 某个值」正好是一句前缀和， 「放进去一个数」正好是一次单点 +1 —— 又改又查，正是这一章的题。

前面比 a[j] 大的个数 = (已经放进去的个数) − (已经放进去的 ≤ a[j] 的个数)
                     = (j − 1) − sum(rank[j])

★ 「相等不算逆序对」这件事就藏在那个 ≤ 里：sum 数的是 ≤ a[j]， 减掉之后剩下的才是严格大于。写成 < 就错了 —— 这是第 22 章 lower_bound / upper_bound 一个字母之差的同款。 ⚠ 而第 11 章的生成器一半的数取自 0..5，重复元素多得很，这个错当场就会被打出来。