前缀和与差分

pre[i] 表示「前 i 个元素的和」(右开,不含 a[i])。花 O(n) 建好后,任何区间和都是一次减法:pre[r+1] - pre[l]——前 r+1 个的和减去前 l 个的和,中间那段就剩下来了。例:a = {3, 1, 4, 1, 5},pre = {0, 3, 4, 8, 9, 14},区间 [1, 3] 的和 = pre[4] - pre[1] = 9 - 3 = 6。被减数下标是 r+1,少 1 就漏掉 a[r]。

差分是前缀和的反操作。要把 a[l..r] 整体加 v,不挨个加,只改差分数组两格:d[l] += v、d[r+1] -= v,不管区间多长都是 O(1)。最后对 d 做一次前缀和就还原出修改后的数组。可以连续多次攒改动、只还原一次,这是差分最省时的用法。

看到「反复区间求和」就想前缀和:把 O(nq) 压到 O(n+q);看到「多次区间整体加」就想差分:同样压到 O(n+q)。两者一个管查询一个管修改,配套记忆。C 里的落点:数组多开一格、pre[0] 手动清零、下标别错位(pre[i] 累加的是 a[i-1])。