尧图网站开发 
Preprefix sum这道题我一直觉得是理解“树状数组”和“二阶差分”之间关系的最佳入门题之一。P4868在洛谷上难度标记是普及说实话题意本身很好懂但你要是真把它当普通前缀和题去写十有八九要超时。我第一次做这道题的时候脑子里冒出来的第一个想法是“前缀和的前缀和那不就是再套一层循环嘛”然后顺利被数据教做人。后来把公式拆开、用两个树状数组分别维护之后才发现这道题真正的价值在于它用最轻量的方式把“动态前缀和”和“差分”这两个概念串在了一起非常值得好好拆一遍。如果你正在学树状数组、已经知道单点修改区间查询那一套基本操作或者被这道题卡过但没太想明白为什么要维护两个东西这篇文章应该能帮你把思路彻底理顺。我会从朴素做法为什么会挂开始一步步推导出核心公式再给出一份可以直接抄的AC代码最后把我在调试过程中踩过的坑和总结出来的通用套路一并列出来保证你看完能自己独立写出来。1. 先看看这道题到底在问什么1.1 题面解读双层前缀和的含义题目定义了一个数组a[1..n]然后给了两个新概念前缀和s[i] a[1] a[2] ... a[i]前缀和的前缀和Preprefix sumss[i] s[1] s[2] ... s[i]说白了就是先对原数组求一次前缀和得到s再对s求一次前缀和得到ss。题目一共支持两种操作操作次数和数组规模都在1e5级别Modify i x把a[i]修改成xQuery i输出ss[i]的值注意这里的修改是“修改成x”不是“加上x”所以处理的时候需要先算出变化量delta这是很多新手容易忽略的细节。为什么会有人觉得这题简单因为前缀和本身就是个线性累加过程那我查询的时候现算一遍ss[i]不就行了修改O(1)查询O(i)最坏情况下查询是O(n)。但题目给了1e5级别的操作数如果来了1e5次查询每次查询都要重新累加1e5个元素那就是1e10次运算必挂无疑。所以这道题的核心痛点就是在支持单点修改的前提下还要快速回答二阶前缀和查询。1.2 朴素做法为什么会超时我们来量化一下暴力到底有多慢。假设n 100000m 100000最坏情况下每次操作都是查询第n个位置的ss值。暴力查询的时候每次都要从a[1]累加到a[n]算s再从s[1]累加到s[n]算ss。虽然可以用一个s数组先预处理好但修改a[i]之后后缀的所有s值都会跟着变所以还是得重算s重算ss。简单估算一下一次查询最坏O(n)m次就是O(n*m)也就是10^10级别。普通OJ一秒大概能跑10^8到10^9次简单运算这个量级显然超时。而且这还只是算加法如果题目数据再强一点直接让你跑到怀疑人生。所以必须找一个“修改和查询都只跟log有关”的数据结构。树状数组或者线段树都满足这一点但树状数组代码短、常数小自然是首选。关键问题是怎么把一个二阶前缀和的东西拆成树状数组最擅长维护的一阶前缀和这就是下一节要解决的核心问题。2. 核心公式推导把二阶前缀和拆成两个一阶量2.1 换序求和从双循环到单循环先看ss[i]的定义ss[i] s[1] s[2] ... s[i]把每个s都展开成a的累加ss[i] a[1] (a[1] a[2]) (a[1] a[2] a[3]) ... (a[1] a[2] ... a[i])如果按列来看a[j]出现在第j行到第i行一共出现了(i - j 1)次。所以可以交换求和顺序ss[i] a[1] * i a[2] * (i-1) ... a[i] * 1也就是ss[i] Σ(j1..i) a[j] * (i - j 1)这个形式已经比双层循环简单多了但它还不是树状数组能直接维护的形式因为每一项都有一个和位置j有关的系数(i - j 1)。这个系数同时包含i和j维护起来不方便。再做一个恒等变形a[j] * (i - j 1) a[j] * (i 1) - a[j] * j所以ss[i] (i 1) * Σ(j1..i) a[j] - Σ(j1..i) j * a[j]到这里核心公式就出来了。你会发现这正好是两个一阶前缀和的线性组合。2.2 维护两个“可累加”的量根据上面的公式我们只需要动态维护两个东西第一个量sumA(i) a[1] a[2] ... a[i]第二个量sumJA(i) 1*a[1] 2*a[2] ... i*a[i]然后每次查询ss[i] (i 1) * sumA(i) - sumJA(i)现在问题变得非常清晰了两个量都是一阶前缀和都可以用树状数组在O(log n)时间内单点修改、前缀查询。当a[x]变成v时令delta v - a[x]那么sumA中从第x个位置开始的所有前缀和都会增加deltasumJA中从第x个位置开始的所有前缀和都会增加x * delta为什么会有“从x开始所有前缀和都会变”这个说法因为树状数组的加操作本质上是往某个坐标打一个增量后面所有包含这个坐标的前缀和查询都会自然带上它。这正好对应了修改a[x]会影响s[x], s[x1], ..., s[n]这个事实。我第一次想通这一点的时候觉得特别爽因为这就是“区间加”在树状数组下的隐藏形态。有人可能会问那第二个量为什么是加x * delta而不是别的因为sumJA里第x项的系数是x所以a[x]变化delta后sumJA的变化量就是x * delta非常直觉。3. 树状数组选型与“二阶差分”的关系3.1 为什么选树状数组而不是线段树很多同学一看到“动态修改区间查询”第一反应是线段树。线段树确实能做这道题维护a数组的区间和以及i*a[i]的区间和但代码量明显比树状数组大不少。这道题里每个操作都是单点修改前缀查询正好是树状数组的主场没必要上线段树。树状数组的核心思想是“二进制拆分的前缀和”它只有两个基本操作add(pos, val)和sum(pos)。前者在pos位置打一个增量后者查询[1, pos]的累计值。单次操作都是O(log n)而且常数非常小代码连十行都不到。对于这种“只需要快速修改、快速查前缀”的题目树状数组就是最优解。顺便说个经验只要题目里没有出现“区间取最大值”“区间赋值”这种需要维护复杂信息的要求优先考虑树状数组。见过太多人看到题就线段树起步结果代码长、调试麻烦最后发现树状数组几行就能搞定得不偿失。3.2 从差分角度理解两个BIT的分工题目标题里带着“二阶差分”这个词容易把人唬住但理解清楚以后其实很自然。我们反过来看a数组做一次前缀和得到ss再做一次前缀和得到ss。那么反过来ss做一阶差分得到ss再做一阶差分得到a。所以这个问题确实是“二阶前缀和”也可以叫“二阶差分的逆问题”。那树状数组和差分有什么关系还记得区间加区间查询的经典套路吗要支持对一个数组区间加c、查询区间和我们维护的是差分数组d[j] b[j] - b[j-1]然后有区间和(1..i) Σ(j1..i) (i - j 1) * d[j] (i 1) * Σd[j] - Σ j*d[j]眼熟不这个形式和上面推出来的公式一模一样区别只在于上面推出来的是对a数组求二阶前缀和而这里是对某个被区间加的数组求一阶前缀和。两者在数学上完全同构所以这道题可以用“区间加区间查询”的思路来理解修改a[x]变成v等价于对s数组执行区间加[x, n]增加量为delta查询ss[i]就是查询s数组的区间和[1, i]而支持“区间加区间查询”的标准工具就是两个树状数组一个维护差分d[j]一个维护j*d[j]这样一来“二阶差分”的名字就名副其实了我们用差分形态的树状数组解决的是一个需要二阶前缀和的问题。奇妙的是推导到最后代码上你只需要维护两个BIT和直接按2.2节理解时写的代码一模一样。这不是巧合而是说明这两种思路本质是一回事——差分和前綏和本来就是一体的两面。所以我个人建议做题时按公式理解维护a和i*a讲思路时按差分理解区间加区间查。两种视角切换熟练了对树状数组的理解会上升一个档次。4. 完整AC代码与逐行精讲4.1 核心代码实现直接上可以AC的C代码我用的是两个树状数组维护a[i]和i*a[i]。这份代码在洛谷P4868上实测可以通过注意看清楚几个乘法都转成了long long。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 100005; int n, m; ll a[MAXN]; ll bit1[MAXN], bit2[MAXN]; // bit1维护a[i]bit2维护i*a[i] void add(ll bit[], int idx, ll val) { while (idx n) { bit[idx] val; idx idx -idx; } } ll sum(ll bit[], int idx) { ll res 0; while (idx 0) { res bit[idx]; idx - idx -idx; } return res; } int main() { scanf(%d%d, n, m); for (int i 1; i n; i) { scanf(%lld, a[i]); add(bit1, i, a[i]); add(bit2, i, 1LL * i * a[i]); } while (m--) { char op[10]; scanf(%s, op); if (op[0] M) { int idx; ll val; scanf(%d%lld, idx, val); ll delta val - a[idx]; // 注意是“改成val”所以要算变化量 a[idx] val; // 一定记得更新原数组 add(bit1, idx, delta); add(bit2, idx, idx * delta); } else { int idx; scanf(%d, idx); ll ans 1LL * (idx 1) * sum(bit1, idx) - sum(bit2, idx); printf(%lld\n, ans); } } return 0; }代码不长但有几个地方我特别想强调。首先是树状数组的add函数idx idx -idx这个操作是在往父节点跳。很多人一开始搞不懂为什么是加lowbit其实你只要记住树状数组的每个节点管理一段区间修改某个位置时所有包含这个位置的区间都要更新。一个位置最多影响O(log n)个节点所以复杂度是对的。同理sum函数里idx - idx -idx是在把查询区间拆成若干段小区间拼出前缀和。这两句话是树状数组的基石建议背下来但更要理解它们的含义。其次是查询那行ans (idx 1) * sum(bit1, idx) - sum(bit2, idx);这就是核心公式的直接落地。sum(bit1, idx)拿到的是Σa[j]sum(bit2, idx)拿到的是Σj*a[j]。两个都是long longidx 1最大也就1e5级别乘以1e10量级的前缀和结果大概是1e15long long完全装得下。但如果你用int这里直接爆掉输出的答案会变成负的我当年就栽在这上面后面会详细讲排错。4.2 手算样例验证光看代码可能还不够踏实咱们拿一个简单数据手动走一遍。假设n5初始数组a [1, 2, 3, 4, 5]先算前缀和s [1, 3, 6, 10, 15]再算二阶前缀和ss [1, 4, 10, 20, 35]也就是ss[4] 20ss[5] 35。现在执行一次修改Modify 2 4把a[2]从2改成4变化量delta 2。新数组a [1, 4, 3, 4, 5]新ss [1, 5, 8, 12, 17]新ssss [1, 6, 14, 26, 43]所以修改后ss[3] 14ss[5] 43。用我们代码的逻辑来验证一下。修改时bit1.add(2, 2)、bit2.add(2, 2*24)。查询ss[3]sum(bit1, 3)应该等于a[1]a[2]a[3] 143 8sum(bit2, 3)应该等于1*1 2*4 3*3 189 18代入公式(31)*8 - 18 32 - 18 14完全正确。这类题写完代码后强烈建议先拿这种小数据手动验一遍确保公式和代码逻辑没接错线再提交。4.3 时空复杂度分析初始化需要n次add操作每次O(log n)总O(n log n)单次修改两次addO(log n)单次查询两次sumO(log n)总复杂度O((nm) log n)n和m都是1e5量级完全轻松通过空间上只用了两个长度为n的long long数组外加原数组a总共O(n)内存约2.4MB左右非常小。这也是树状数组比线段树有优势的地方之一不仅代码短空间还省。5. 常见问题与实战排错5.1 五个最容易踩的坑第一个坑忘开long long。这个问题我在前面反复强调因为真的太容易犯了。ss[i]的最大值大概是n * Σa[i]如果a[i]给到1e5量级n也是1e5那结果就是1e15早超过int范围了。最气人的是有时候数据弱一点int也能过一旦数据强了答案突然变成负数排查半天才找到是类型问题。所以代码里凡是涉及累加和乘法的变量一律用long long别给自己留隐患。第二个坑修改操作写成加值而不是赋值。题面说的是Modify i x表示把a[i]修改成x所以一定要算delta也就是delta x - a[i]。如果你直接往BIT里加x那就变成“把a[i]加上x”了样例都过不了。这个错误很隐蔽因为样例可能刚好让你觉得数字对不上但又不知道哪里错了。第三个坑忘了更新原数组a[i]。修改完之后a[i]必须立刻更新成新值否则下一次修改时算出来的delta就是基于旧值的整个数据就乱了。这种bug特别难发现因为错误只会在连续两次修改同一个位置时暴露。我的习惯是a[idx] val写在所有add操作之前这样就算后面代码写崩了原数组也是最新的。第四个坑查询时把(idx1) * sum(bit1, idx)写反了。公式是ss[i] (i1)*sumA(i) - sumJA(i)注意是idx1乘第一个BIT不是乘第二个。初学者很容易把两个BIT搞混结果答案错得离谱。如果发现自己算出来的数特别大或者特别小先检查一下是不是把bit1和bit2的位置写反了。第五个坑数组越界。树状数组的add循环条件是idx n如果你在n1的位置也做add会越界访问。虽然本题只改一个点用不到n1但如果你未来扩展成区间修改写法需要处理n1位置的减法时记得把数组开大一点或者直接忽略n1的更新因为查询下标永远不会超过n。我习惯把BIT数组在原来基础上多开几个单位省心。5.2 扩展从单点修改到区间修改掌握了这道题的核心公式之后你会发现它的强大之处在于可以轻松扩展。假设题目不是单点修改而是给一个区间[l, r]整体加上v问ss[i]怎么做其实只需要把add操作从单点改成差分区间加的形式// 对[l, r]整体加v影响sumA和sumJA add(bit1, l, v); add(bit1, r 1, -v); add(bit2, l, v * l); add(bit2, r 1, -v * (r 1));原理也很简单区间[l, r]整体加v放在差分视角下就是在差分数组的l位置加v、r1位置减v。而树状数组单点add天然支持这个操作。查询公式完全不用变。这就是为什么我说差分视角理解这题很重要——它能让你从“单点修改”平滑过渡到“区间修改”这种更复杂的场景思路完全不用换。如果再进一步题目要求查询的是任意区间[L, R]的ss和你只需要回答两个前缀查询然后相减query(R) - query(L-1)。树状数组的前缀和模型天然支持这种操作。5.3 这类题的通用套路做完P4868之后我总结了一套“前缀和类题目”的通用解题套路分享给大家先写公式别急着写代码。把要求的东西用数学表达式写出来能展开就展开能换序就换序目标是拆成若干个“一阶前缀和”的加减组合。看拆出来的是什么量。如果每个量都能用树状数组的单点修改区间查询维护那直接上BIT一个量一个BIT。修改操作对应到BIT上无非是两种写法。单点修改就是add(pos, delta)区间修改就是差分法add(l, delta) add(r1, -delta)本质都一样。不要被题目名字吓到。“前缀和的前缀和”听起来吓人但你拆开就会发现不过是(i1)*Σa - Σi*a这么简单。以后再遇到“二阶”“三阶”的类似题拆就完了公式写出来代码自然就出来了。遇到同样思维模式的题还有很多比如动态求区间和、带修改的逆序对计数、二维树状数组求子矩阵和等等。核心思想不变把高级操作拆成低级操作的组合用数据结构维护低级操作再把答案拼回去。结尾最后再分享一个我自己做题时的小习惯这类公式推导题我一般会在草稿纸上把题目给的原始定义展开成矩阵形式。就像2.1节里那样把s的每一项竖着写出来然后横向看每个a[j]出现了几次。这个过程一开始会觉得有点麻烦但多练几次之后特别快而且几乎不会推错。相比之下如果你直接背公式一旦题目换一个系数、换一个定义很容易翻车。P4868虽然难度标的是普及但它对“公式推导数据结构维护”这个组合能力的训练价值很高。我自己做完这道题之后再看区间修改区间查询的树状数组模板题理解就通透了很多——因为它们的核心公式长得一模一样。如果你现在正卡在这道题上别急先把这篇的推导按自己的话写一遍再把代码敲一遍然后去洛谷交一发。相信我亲手AC之后的那种舒畅感值得你花这几十分钟。 
Preprefix sum这道题我一直觉得是理解“树状数组”和“二阶差分”之间关系的最佳入门题之一。P4868在洛谷上难度标记是普及说实话题意本身很好懂但你要是真把它当普通前缀和题去写十有八九要超时。我第一次做这道题的时候脑子里冒出来的第一个想法是“前缀和的前缀和那不就是再套一层循环嘛”然后顺利被数据教做人。后来把公式拆开、用两个树状数组分别维护之后才发现这道题真正的价值在于它用最轻量的方式把“动态前缀和”和“差分”这两个概念串在了一起非常值得好好拆一遍。如果你正在学树状数组、已经知道单点修改区间查询那一套基本操作或者被这道题卡过但没太想明白为什么要维护两个东西这篇文章应该能帮你把思路彻底理顺。我会从朴素做法为什么会挂开始一步步推导出核心公式再给出一份可以直接抄的AC代码最后把我在调试过程中踩过的坑和总结出来的通用套路一并列出来保证你看完能自己独立写出来。1. 先看看这道题到底在问什么1.1 题面解读双层前缀和的含义题目定义了一个数组a[1..n]然后给了两个新概念前缀和s[i] a[1] a[2] ... a[i]前缀和的前缀和Preprefix sumss[i] s[1] s[2] ... s[i]说白了就是先对原数组求一次前缀和得到s再对s求一次前缀和得到ss。题目一共支持两种操作操作次数和数组规模都在1e5级别Modify i x把a[i]修改成xQuery i输出ss[i]的值注意这里的修改是“修改成x”不是“加上x”所以处理的时候需要先算出变化量delta这是很多新手容易忽略的细节。为什么会有人觉得这题简单因为前缀和本身就是个线性累加过程那我查询的时候现算一遍ss[i]不就行了修改O(1)查询O(i)最坏情况下查询是O(n)。但题目给了1e5级别的操作数如果来了1e5次查询每次查询都要重新累加1e5个元素那就是1e10次运算必挂无疑。所以这道题的核心痛点就是在支持单点修改的前提下还要快速回答二阶前缀和查询。1.2 朴素做法为什么会超时我们来量化一下暴力到底有多慢。假设n 100000m 100000最坏情况下每次操作都是查询第n个位置的ss值。暴力查询的时候每次都要从a[1]累加到a[n]算s再从s[1]累加到s[n]算ss。虽然可以用一个s数组先预处理好但修改a[i]之后后缀的所有s值都会跟着变所以还是得重算s重算ss。简单估算一下一次查询最坏O(n)m次就是O(n*m)也就是10^10级别。普通OJ一秒大概能跑10^8到10^9次简单运算这个量级显然超时。而且这还只是算加法如果题目数据再强一点直接让你跑到怀疑人生。所以必须找一个“修改和查询都只跟log有关”的数据结构。树状数组或者线段树都满足这一点但树状数组代码短、常数小自然是首选。关键问题是怎么把一个二阶前缀和的东西拆成树状数组最擅长维护的一阶前缀和这就是下一节要解决的核心问题。2. 核心公式推导把二阶前缀和拆成两个一阶量2.1 换序求和从双循环到单循环先看ss[i]的定义ss[i] s[1] s[2] ... s[i]把每个s都展开成a的累加ss[i] a[1] (a[1] a[2]) (a[1] a[2] a[3]) ... (a[1] a[2] ... a[i])如果按列来看a[j]出现在第j行到第i行一共出现了(i - j 1)次。所以可以交换求和顺序ss[i] a[1] * i a[2] * (i-1) ... a[i] * 1也就是ss[i] Σ(j1..i) a[j] * (i - j 1)这个形式已经比双层循环简单多了但它还不是树状数组能直接维护的形式因为每一项都有一个和位置j有关的系数(i - j 1)。这个系数同时包含i和j维护起来不方便。再做一个恒等变形a[j] * (i - j 1) a[j] * (i 1) - a[j] * j所以ss[i] (i 1) * Σ(j1..i) a[j] - Σ(j1..i) j * a[j]到这里核心公式就出来了。你会发现这正好是两个一阶前缀和的线性组合。2.2 维护两个“可累加”的量根据上面的公式我们只需要动态维护两个东西第一个量sumA(i) a[1] a[2] ... a[i]第二个量sumJA(i) 1*a[1] 2*a[2] ... i*a[i]然后每次查询ss[i] (i 1) * sumA(i) - sumJA(i)现在问题变得非常清晰了两个量都是一阶前缀和都可以用树状数组在O(log n)时间内单点修改、前缀查询。当a[x]变成v时令delta v - a[x]那么sumA中从第x个位置开始的所有前缀和都会增加deltasumJA中从第x个位置开始的所有前缀和都会增加x * delta为什么会有“从x开始所有前缀和都会变”这个说法因为树状数组的加操作本质上是往某个坐标打一个增量后面所有包含这个坐标的前缀和查询都会自然带上它。这正好对应了修改a[x]会影响s[x], s[x1], ..., s[n]这个事实。我第一次想通这一点的时候觉得特别爽因为这就是“区间加”在树状数组下的隐藏形态。有人可能会问那第二个量为什么是加x * delta而不是别的因为sumJA里第x项的系数是x所以a[x]变化delta后sumJA的变化量就是x * delta非常直觉。3. 树状数组选型与“二阶差分”的关系3.1 为什么选树状数组而不是线段树很多同学一看到“动态修改区间查询”第一反应是线段树。线段树确实能做这道题维护a数组的区间和以及i*a[i]的区间和但代码量明显比树状数组大不少。这道题里每个操作都是单点修改前缀查询正好是树状数组的主场没必要上线段树。树状数组的核心思想是“二进制拆分的前缀和”它只有两个基本操作add(pos, val)和sum(pos)。前者在pos位置打一个增量后者查询[1, pos]的累计值。单次操作都是O(log n)而且常数非常小代码连十行都不到。对于这种“只需要快速修改、快速查前缀”的题目树状数组就是最优解。顺便说个经验只要题目里没有出现“区间取最大值”“区间赋值”这种需要维护复杂信息的要求优先考虑树状数组。见过太多人看到题就线段树起步结果代码长、调试麻烦最后发现树状数组几行就能搞定得不偿失。3.2 从差分角度理解两个BIT的分工题目标题里带着“二阶差分”这个词容易把人唬住但理解清楚以后其实很自然。我们反过来看a数组做一次前缀和得到ss再做一次前缀和得到ss。那么反过来ss做一阶差分得到ss再做一阶差分得到a。所以这个问题确实是“二阶前缀和”也可以叫“二阶差分的逆问题”。那树状数组和差分有什么关系还记得区间加区间查询的经典套路吗要支持对一个数组区间加c、查询区间和我们维护的是差分数组d[j] b[j] - b[j-1]然后有区间和(1..i) Σ(j1..i) (i - j 1) * d[j] (i 1) * Σd[j] - Σ j*d[j]眼熟不这个形式和上面推出来的公式一模一样区别只在于上面推出来的是对a数组求二阶前缀和而这里是对某个被区间加的数组求一阶前缀和。两者在数学上完全同构所以这道题可以用“区间加区间查询”的思路来理解修改a[x]变成v等价于对s数组执行区间加[x, n]增加量为delta查询ss[i]就是查询s数组的区间和[1, i]而支持“区间加区间查询”的标准工具就是两个树状数组一个维护差分d[j]一个维护j*d[j]这样一来“二阶差分”的名字就名副其实了我们用差分形态的树状数组解决的是一个需要二阶前缀和的问题。奇妙的是推导到最后代码上你只需要维护两个BIT和直接按2.2节理解时写的代码一模一样。这不是巧合而是说明这两种思路本质是一回事——差分和前綏和本来就是一体的两面。所以我个人建议做题时按公式理解维护a和i*a讲思路时按差分理解区间加区间查。两种视角切换熟练了对树状数组的理解会上升一个档次。4. 完整AC代码与逐行精讲4.1 核心代码实现直接上可以AC的C代码我用的是两个树状数组维护a[i]和i*a[i]。这份代码在洛谷P4868上实测可以通过注意看清楚几个乘法都转成了long long。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 100005; int n, m; ll a[MAXN]; ll bit1[MAXN], bit2[MAXN]; // bit1维护a[i]bit2维护i*a[i] void add(ll bit[], int idx, ll val) { while (idx n) { bit[idx] val; idx idx -idx; } } ll sum(ll bit[], int idx) { ll res 0; while (idx 0) { res bit[idx]; idx - idx -idx; } return res; } int main() { scanf(%d%d, n, m); for (int i 1; i n; i) { scanf(%lld, a[i]); add(bit1, i, a[i]); add(bit2, i, 1LL * i * a[i]); } while (m--) { char op[10]; scanf(%s, op); if (op[0] M) { int idx; ll val; scanf(%d%lld, idx, val); ll delta val - a[idx]; // 注意是“改成val”所以要算变化量 a[idx] val; // 一定记得更新原数组 add(bit1, idx, delta); add(bit2, idx, idx * delta); } else { int idx; scanf(%d, idx); ll ans 1LL * (idx 1) * sum(bit1, idx) - sum(bit2, idx); printf(%lld\n, ans); } } return 0; }代码不长但有几个地方我特别想强调。首先是树状数组的add函数idx idx -idx这个操作是在往父节点跳。很多人一开始搞不懂为什么是加lowbit其实你只要记住树状数组的每个节点管理一段区间修改某个位置时所有包含这个位置的区间都要更新。一个位置最多影响O(log n)个节点所以复杂度是对的。同理sum函数里idx - idx -idx是在把查询区间拆成若干段小区间拼出前缀和。这两句话是树状数组的基石建议背下来但更要理解它们的含义。其次是查询那行ans (idx 1) * sum(bit1, idx) - sum(bit2, idx);这就是核心公式的直接落地。sum(bit1, idx)拿到的是Σa[j]sum(bit2, idx)拿到的是Σj*a[j]。两个都是long longidx 1最大也就1e5级别乘以1e10量级的前缀和结果大概是1e15long long完全装得下。但如果你用int这里直接爆掉输出的答案会变成负的我当年就栽在这上面后面会详细讲排错。4.2 手算样例验证光看代码可能还不够踏实咱们拿一个简单数据手动走一遍。假设n5初始数组a [1, 2, 3, 4, 5]先算前缀和s [1, 3, 6, 10, 15]再算二阶前缀和ss [1, 4, 10, 20, 35]也就是ss[4] 20ss[5] 35。现在执行一次修改Modify 2 4把a[2]从2改成4变化量delta 2。新数组a [1, 4, 3, 4, 5]新ss [1, 5, 8, 12, 17]新ssss [1, 6, 14, 26, 43]所以修改后ss[3] 14ss[5] 43。用我们代码的逻辑来验证一下。修改时bit1.add(2, 2)、bit2.add(2, 2*24)。查询ss[3]sum(bit1, 3)应该等于a[1]a[2]a[3] 143 8sum(bit2, 3)应该等于1*1 2*4 3*3 189 18代入公式(31)*8 - 18 32 - 18 14完全正确。这类题写完代码后强烈建议先拿这种小数据手动验一遍确保公式和代码逻辑没接错线再提交。4.3 时空复杂度分析初始化需要n次add操作每次O(log n)总O(n log n)单次修改两次addO(log n)单次查询两次sumO(log n)总复杂度O((nm) log n)n和m都是1e5量级完全轻松通过空间上只用了两个长度为n的long long数组外加原数组a总共O(n)内存约2.4MB左右非常小。这也是树状数组比线段树有优势的地方之一不仅代码短空间还省。5. 常见问题与实战排错5.1 五个最容易踩的坑第一个坑忘开long long。这个问题我在前面反复强调因为真的太容易犯了。ss[i]的最大值大概是n * Σa[i]如果a[i]给到1e5量级n也是1e5那结果就是1e15早超过int范围了。最气人的是有时候数据弱一点int也能过一旦数据强了答案突然变成负数排查半天才找到是类型问题。所以代码里凡是涉及累加和乘法的变量一律用long long别给自己留隐患。第二个坑修改操作写成加值而不是赋值。题面说的是Modify i x表示把a[i]修改成x所以一定要算delta也就是delta x - a[i]。如果你直接往BIT里加x那就变成“把a[i]加上x”了样例都过不了。这个错误很隐蔽因为样例可能刚好让你觉得数字对不上但又不知道哪里错了。第三个坑忘了更新原数组a[i]。修改完之后a[i]必须立刻更新成新值否则下一次修改时算出来的delta就是基于旧值的整个数据就乱了。这种bug特别难发现因为错误只会在连续两次修改同一个位置时暴露。我的习惯是a[idx] val写在所有add操作之前这样就算后面代码写崩了原数组也是最新的。第四个坑查询时把(idx1) * sum(bit1, idx)写反了。公式是ss[i] (i1)*sumA(i) - sumJA(i)注意是idx1乘第一个BIT不是乘第二个。初学者很容易把两个BIT搞混结果答案错得离谱。如果发现自己算出来的数特别大或者特别小先检查一下是不是把bit1和bit2的位置写反了。第五个坑数组越界。树状数组的add循环条件是idx n如果你在n1的位置也做add会越界访问。虽然本题只改一个点用不到n1但如果你未来扩展成区间修改写法需要处理n1位置的减法时记得把数组开大一点或者直接忽略n1的更新因为查询下标永远不会超过n。我习惯把BIT数组在原来基础上多开几个单位省心。5.2 扩展从单点修改到区间修改掌握了这道题的核心公式之后你会发现它的强大之处在于可以轻松扩展。假设题目不是单点修改而是给一个区间[l, r]整体加上v问ss[i]怎么做其实只需要把add操作从单点改成差分区间加的形式// 对[l, r]整体加v影响sumA和sumJA add(bit1, l, v); add(bit1, r 1, -v); add(bit2, l, v * l); add(bit2, r 1, -v * (r 1));原理也很简单区间[l, r]整体加v放在差分视角下就是在差分数组的l位置加v、r1位置减v。而树状数组单点add天然支持这个操作。查询公式完全不用变。这就是为什么我说差分视角理解这题很重要——它能让你从“单点修改”平滑过渡到“区间修改”这种更复杂的场景思路完全不用换。如果再进一步题目要求查询的是任意区间[L, R]的ss和你只需要回答两个前缀查询然后相减query(R) - query(L-1)。树状数组的前缀和模型天然支持这种操作。5.3 这类题的通用套路做完P4868之后我总结了一套“前缀和类题目”的通用解题套路分享给大家先写公式别急着写代码。把要求的东西用数学表达式写出来能展开就展开能换序就换序目标是拆成若干个“一阶前缀和”的加减组合。看拆出来的是什么量。如果每个量都能用树状数组的单点修改区间查询维护那直接上BIT一个量一个BIT。修改操作对应到BIT上无非是两种写法。单点修改就是add(pos, delta)区间修改就是差分法add(l, delta) add(r1, -delta)本质都一样。不要被题目名字吓到。“前缀和的前缀和”听起来吓人但你拆开就会发现不过是(i1)*Σa - Σi*a这么简单。以后再遇到“二阶”“三阶”的类似题拆就完了公式写出来代码自然就出来了。遇到同样思维模式的题还有很多比如动态求区间和、带修改的逆序对计数、二维树状数组求子矩阵和等等。核心思想不变把高级操作拆成低级操作的组合用数据结构维护低级操作再把答案拼回去。结尾最后再分享一个我自己做题时的小习惯这类公式推导题我一般会在草稿纸上把题目给的原始定义展开成矩阵形式。就像2.1节里那样把s的每一项竖着写出来然后横向看每个a[j]出现了几次。这个过程一开始会觉得有点麻烦但多练几次之后特别快而且几乎不会推错。相比之下如果你直接背公式一旦题目换一个系数、换一个定义很容易翻车。P4868虽然难度标的是普及但它对“公式推导数据结构维护”这个组合能力的训练价值很高。我自己做完这道题之后再看区间修改区间查询的树状数组模板题理解就通透了很多——因为它们的核心公式长得一模一样。如果你现在正卡在这道题上别急先把这篇的推导按自己的话写一遍再把代码敲一遍然后去洛谷交一发。相信我亲手AC之后的那种舒畅感值得你花这几十分钟。