区间求和

一句话理解

区间求和用前缀和变成两次下标运算。

为什么要学

查询多次时必做。

讲解

不要每次从 l 加到 r。n 和 q 都是 1e5 就会 TLE。

先确认是静态数组，没有中间修改；有修改要用树状数组或线段树。

例子

a=[1,2,3,4]，s=[0,1,3,6,10]。区间 [2,4] = 10-1=9。

常见错误

• 有单点修改仍用静态前缀和。
• l=1 时写 s[l-1] 却没准备 s[0]。