交互演示:区间求和
n = 5
原数组 a
前缀和数组 s
原数组从 a
0
开始。s
0
= 0,s
i
= s
i−1
+ a
i−1
,表示前 i 项之和。
绿色:取 s
r+1
,
橙色:减去 s
l
,剩下的就是区间 [l, r] 的和。
左端点 l
右端点 r
利用前缀和