前缀和回顾

前缀和 s[i]=a[1]+…+a[i]，区间和 a[l..r]=s[r]-s[l-1]，查询 O(1)，预处理 O(n)。它是很多区间数据结构的思想起点：把“区间和”变成“两个前缀和相减”。