一维前缀和

一句话理解

一维前缀和：s[i]=a[1]+…+a[i]。

为什么要学

区间求和的预处理。非常值得优先学。

讲解

s[0]=0，s[i]=s[i-1]+a[i]。求 a[l]+…+a[r] = s[r]-s[l-1]。

用 long long。下标从 1 更不容易碰到 l-1。

例子

for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
cout << s[r] - s[l - 1];

预处理 O(n)，每次查询 O(1)。

常见错误

• s[r]-s[l] 少加了 a[l]。
• int 求和溢出。