【模板】序列前缀和

深碍√TFBOYSˉ_ 2023-07-06 11:44 16阅读 0赞

# Description #

你需要维护 N 个整数组成的序列，支持 Q 次询问，每次询问区间 \[l,r\] 的数字之和是多少.

# Input #

第一行两个整数 N，Q.  
接下来一行 N 个数字，表示序列的初始值是多少.  
接下来 Q 行，每行两个整数 l , r.

# Output #

输出 Q 行，每行一个整数，代表对应区间的元素之和.

# Sample Input #

5 2
    1 2 3 4 5
    1 3
    3 5

Copy

# Sample Output #

6
    12

Copy

# Hint #

`0<=N,Q<=100000,a[i]<=1e9`  
常数尽量小吧，要不很容易被卡.

> 本题不能用cin、cout输入输出，否则会超时。即使使用下面的两条语句优化加速后也会超时：
> 
> ios::sync\_with\_stdio(false);  
> cin.tie(0);cout.tie(0);

#include<iostream>
    #include<cstdio>
    #define N 100005
    long long a[N];
    int main()
    {
    	int n,q;
    	scanf("%d%d",&n,&q);
    	long long x;
    	for(int i = 1; i <= n; ++i)
    	{
    		scanf("%lld",&x);
    		a[i]= a[i-1] + x;
    	}
    	int l,r;
    	while(q--)
    	{
    		scanf("%d%d",&l,&r);
    		//cout << a[r]-a[l-1] << endl;
    		printf("%lld\n",a[r]-a[l-1]);
    	}
    	return 0;
    }

#include<iostream>
    #include<cstdio>
    #define N 100005
    long long a[N];
    int main()
    {
    	int n,q;
    	scanf("%d%d",&n,&q);
    	//long long x;
    	for(int i = 1; i <= n; ++i)
    	{
    		scanf("%lld",&a[i]);
    		a[i]= a[i-1] + a[i];
    	}
    	int l,r;
    	while(q--)
    	{
    		scanf("%d%d",&l,&r);
    		//cout << a[r]-a[l-1] << endl;
    		printf("%lld\n",a[r]-a[l-1]);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，16人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|前缀和系列No.2】牛客网 DP35 【模板】二维前缀和

【算法|前缀和系列No.2】牛客网 DP35 【模板】二维前缀和

╰半橙微兮°/ 2024年04月27日 06:37/ 0 赞/ 109 阅读

相关【算法|前缀和系列No.1】牛客网 DP34 【模板】前缀和

【算法|前缀和系列No.1】牛客网 DP34 【模板】前缀和

Bertha 。/ 2024年04月27日 06:36/ 0 赞/ 111 阅读

相关前缀和模板

class Solution { public void func(int[] nums) { int n = nums.len

逃离我推掉我的手/ 2024年03月25日 10:02/ 0 赞/ 136 阅读

相关【算法挨揍日记】day13—— DP34 【模板】前缀和、DP35 【模板】二维前缀和

![570b75578b874e4bb492c02f62a95442.png][] DP34 【模板】前缀和 [【模板】前缀和\_牛客题霸\_牛客网][Link 1]

Dear 丶/ 2024年02月25日 02:32/ 0 赞/ 84 阅读

相关一、基础算法5：前缀和与差分模板题+算法模板（前缀和，子矩阵的和，差分，差分矩阵）

文章目录算法模板前缀和模板子矩阵的和模板差分模板差分矩阵模板模板题前缀和

左手的ㄟ右手/ 2023年10月08日 23:25/ 0 赞/ 84 阅读

相关单调队列 + 前缀和：连续子序列的最大和

单调队列 + 前缀和：连续子序列的最大和文章目录单调队列 + 前缀和：连续子序列的最大和单调队列问题：

逃离我推掉我的手/ 2023年10月06日 19:43/ 0 赞/ 59 阅读

相关【模板】序列前缀和

Description 你需要维护 N 个整数组成的序列，支持 Q 次询问，每次询问区间 \[l,r\] 的数字之和是多少. Input 第一行两个整数 N，Q.

深碍√TFBOYSˉ_/ 2023年07月06日 11:44/ 0 赞/ 17 阅读

相关 LeetCode 208. 实现 Trie (前缀树) —— 提供一套前缀树模板

[208. 实现 Trie (前缀树)][208. _ Trie] Ideas 前缀树嘛，直接套模板咯，把之前写的拿过来抄一遍。提供一下我的模板。 Code

迷南。/ 2022年11月19日 04:12/ 0 赞/ 198 阅读

相关 18927 前缀和

题目描述前缀和是一种重要的预处理方法，能极大地降低查询序列区间和的时间复杂度。现在一个序列中有n个整数，下标从1…n。有m个查询，每个查询给出一个区间的左右

蔚落/ 2022年11月13日 04:11/ 0 赞/ 225 阅读

相关 05前缀和模板

> 前缀和模板 : > 前缀呢无非就是从left->right的和 = s\[right\] - s\[left-1\]![watermark_type_ZHJv

柔情只为你懂/ 2022年09月12日 15:54/ 0 赞/ 188 阅读