差分数组

查找与遍历

说明

在区间两端标记变化；批量区间加法后一次前缀和还原，时间 O(n+q)。

分析

对 [l,r) 加 delta，只需在 l 处加 delta、r 处减 delta。所有更新记录完后做一次前缀累加，即可恢复每个位置的最终值。

对长度4的零数组在[1,3)加5，只在1记录开始增加，在3记录停止增加。累加时1、2位置均得到5，位置3恢复0。额外槽支持r=n；非零原数组需先构造差分或将更新量加回原值。

查看图表代码

适用前提与边界

它适合离线批量更新；若更新之间要立即查询，应换用支持在线操作的数据结构。 每条更新须满足0≤l≤r≤n；空区间不改变结果，空更新列表得到长度n的零数组。累计增量要避免int溢出，更新间要立即查询时应另选在线结构。

示例输入与调用

fmt.Println(RangeAdds(4, [][3]int{{1, 3, 5}}))

运行输出

[0 5 5 0]

完整 Go 示例

package main

import "fmt"

func RangeAdds(n int, updates [][3]int) []int {
	diff := make([]int, n+1)
	for _, u := range updates {
		diff[u[0]] += u[2]
		diff[u[1]] -= u[2]
	}
	out := make([]int, n)
	s := 0
	for i := range out {
		s += diff[i]
		out[i] = s
	}
	return out
}

func main() {
	fmt.Println(RangeAdds(4, [][3]int{{1, 3, 5}}))
}