假设原始数组为a,长度为n。对于i从1到n,计算出前i个元素之和,并存储在S[i]中。可以发现,对于任意一段区间[l, r](其中1 <= l <= r <= n),其和可以表示为S[r] - S[l - 1]。
这个结论的证明很简单:区间[l, r]中的所有元素之和等于前r个元素之和减去前l-1个元素之和。
因此,如果需要多次查询不同的子数组和,则可以预处理出前缀和数组S,并在O(1)时间内回答每个查询。这种方法的时间复杂度是O(n)(预处理)+ O(1)(每次查询),总体时间复杂度是O(n)。
下面是代码实现:
// 计算前缀和数组S
for (int i = 1; i <= n; i++) S[i] = S[i-1] + a[i];
// 查询区间[l, r]的元素之和
int sum = S[r] - S[l-1];