前缀和
设 Si = A1 + A2 + ··· + Ai，其中 Si 就是叫做位置 i 的前缀和。
int[] a = new int[n]; int[] x = new int[n]; for (int i = 0; i < n; ++i) { a[i] = nextInt(); x[i] = i>0?x[i-1] + a[i]:a[i];// 前缀和的计算 }
前缀和应用
Ai + Ai+1 + ··· + Aj = Sj - Si-1，其直观含义是连续子序列之和等于两个前缀和之差。我们可以利用这个性质优化某些循环，例如最大子段和。
