前缀和与差分

前缀和是一种极其优秀的线性结构，也是一种重要的思想，能极大地降低区间查询的时间复杂度。 一维前缀和 1 2 S[i] = a[1] + a[2] + ... a[i] a[l] + ... + a[r] = S[r] - S[l - 1] 最...