【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)
目录
🚩了解题意
🚩算法原理
🎈设定下标为1开始
🎈取值的范围
🚩实现代码
🚩了解题意
第一行的3和2,3代表行数,2代表q次查询(查询的次数)
第二行 1 2 4 表示 n=3个整数 (长度为n的数组各个数)
第三行和第四行(有几行代表几次查询) 分别是1,2和 2,3
- (1,2)代表第一次查询 从1到2(这里我们需要注意下标要从1开始)所以我们相加的是1+2=3 第一次结果是3。
- (2,3)代表第二次查询从2到3 所以相加的是2+4=6 第二次结果是6.
🚩算法原理
如果有q次查询,我们需要依次q--,再一次循环中依次输入l和r的值。
- 输入:从标准输入中读取两个整数
n
和q
,分别表示数组的大小和查询的次数。- 数组初始化:创建一个大小为
n+1
的数组arr
,用于存储输入的数组元素。同时创建一个大小为n+1
的数组dp
,用于存储前缀和。注意,数组从索引1
开始存储元素,而不是从0
开始。- 计算前缀和:遍历输入的数组元素,计算每个位置
i
的前缀和,并存储在dp[i]
中。具体做法是,对于每个位置i
,将前i
个元素的和累加到dp[i]
中。这样,dp[i]
就表示数组前i
个元素的和。- 处理查询:循环
q
次,每次读取一个查询的左右边界l
和r
。然后,通过前缀和数组dp
,计算子数组arr[l...r]
的和,即dp[r] - dp[l-1]
。这是因为dp[r]
包含了arr[1...r]
的和,而dp[l-1]
包含了arr[1...l-1]
的和,两者相减即可得到arr[l...r]
的和。- 输出结果:将每次查询得到的子数组和输出到标准输出中。
🎈设定下标为1开始
我们需要将下标设定是1开始的,我们平常的数组定义是第一个数的下标是0,而这里我们需要手动设定下标从1开始 vector<int>(n+1)
数组初始化:创建一个大小为 n+1
的数组 arr
,用于存储输入的数组元素。同时创建一个大小为 n+1
的数组 dp
,用于存储前缀和。注意,数组从索引 1
开始存储元素,而不是从 0
开始。
🎈取值的范围
这里我们看到数组中的取值是-10^9~10^9,所以我们需要用到long long 而不是int类型
🚩实现代码
#include <iostream>
#include<vector>
using namespace std;
int main()
{
long long n,q;
cin>>n>>q;
vector<long long>arr(n+1);
for(long long i=1;i<=n;i++)cin>>arr[i];
//2.预处理一个前缀和数组
vector<long long>dp(n+1);
for(long long i=1;i<=n;i++)dp[i]=dp[i-1]+arr[i];
//3.使用前缀和数组
long long l=0,r=0;
while(q--)
{
cin>>l>>r;
cout<<dp[r]-dp[l-1]<<endl;
}
return 0;
}
不要过度美化没走的那条路。