前缀和
具体做法：
首先做一个预处理，定义一个sum[]数组，sum[i]代表a数组中前i个数的和。
求前缀和运算：
const int N = 1e5+10;
int sum[N], a[N]; //sum[i] = a[1] + a[2] + a[3] ..... a[i];
for(int i = 1; i <= n;i++)
{
sum[i] = sum[i - 1] + a[i];
}
然后查询操作：
scanf("%d%d", &l, &r);
printf("%d\n", sum[r] - sum[l - 1]);
对于每次查询，只需执行sum[r] - sum[l - 1] ，时间复杂度为O(1)
原理
sum[r] = a[1] + a[2] + a[3] + a[l-1] + a[l] + a[l+1] ...... a[r];
sum[l - 1] = a[1] + a[2] + a[3] + a[l - 1];
sum[r] - sum[l - 1] = a[l] + a[l + 1]+......+ a[r];
图解
这样，对于每个询问，只需要执行 sum[r]-sum[l-1]。输出原序列中从第l个数到第r个数的和的时间复杂度变成了O(1)。
我们把它叫做一维前缀和。
总结：
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],sum[N];
int main()
{
int n,m,x;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>x;
sum[i]=x+sum[i-1];
}
while(m--)
{
int l,r;
cin>>l>>r;
cout<<sum[r]-sum[l-1]<<endl;
}
return 0;
}
问一下，这题循环输入那里用0~n-1的话，为什么过不了呢，这俩不是一样的吗？
循环输入用0~n-1的话，由于前缀和s[i] = s[i - 1] + a[i]， 那么求第一个数的前缀和的时候 ：s[0] = s[-1] + a[0]，数组下标是从0开始的哦，没有-1这个下标
stO
❤️
各位大佬，我浅浅问一下sum[0]是多少，没有赋值的话不会把内存中之前存储的数据赋值给sum[0]吗？为啥这里的sum[0]是0呢？哪位大佬能给我解惑一下，跪求
全局变量默认初值是0。如果
sum在这不被定义成全局，而是主函数内定义且不赋初值，则是随机数。学习总结了一、二维前缀和差分，希望对你有帮助~
https://blog.csdn.net/m0_74215326/article/details/129620912?spm=1001.2014.3001.5502
为什么不能只遍历 l,r然后直接算呢？大概就是for(int i = l;i <= r;i ++);sum += a[i];这样子算呢？
速度太慢
超时
多定义了一个没有用到的变量 a
#include[HTML_REMOVED]是啥意思
好妙的x
这个a[N]有什么用
meiyong
天才
太感谢了！
逻辑清晰
太详细了！感谢！
线段树思想
sum减sum可太创新了
逻辑清晰，爱了爱了