前缀和算法可以理解为是一种以空间换时间的方式，通过一个新的数组来存储从头到当前位置的数据量的总和。假设a数组为原数组，s数组是前缀和数组，那么s[i] = s[i-1]+a[i]。由此数组的有效数据应该从下标1开始。如此初始化之后，求区间和便可以优化到O(1)，便可得到s[R] = s[1]+s[2]+...+s[R]，s[L-1] = s[1]+s[2]+...+s[L-1]。若要求求 L 到 R 的区间和，就等于s[R] - s[L-1]。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 100010; int n,m; int back[N],arr[N]; int main() { scanf("%d%d",&n,&m); for(int i = 1;i<=n;i++) { scanf("%d",&arr[i]); back[i] = back[i-1] + arr[i]; //初始化前缀和数组 } while(m--) { int l,r; scanf("%d%d",&l,&r); printf("%d\n",back[r]-back[l-1]); //计算区间和 } return 0; }
