题意整理。
给定一个长度为n的数组。
有q次查询，每次查询给定左右边界l和r，输出下标在l、r之间的所有元素的累加和。
方法一（前缀和）
1.解题思路
首先对数组进行预处理，得到对应的前缀和数组。
利用前缀和数组r下标对应的值减去l-1下标对应的值，即可得到下标在l、r之间的所有元素的累加和。
展开全文
【模板】前缀和
难度：2星
前缀和模板题。我们定义 sum[i]sum[i]sum[i] 为前 iii 个数之和，可以通过预处理 O(n)O(n)O(n) 求出所有的 sum[i]sum[i]sum[i]，那么查询区间 [l,r][l,r][l,r] 中所有数之和只需要输出 sum[r]−sum[l
展开全文
#牛客春招刷题训练营#
https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?channelPut=w25springcamp
观察本题，我们可以通过线段树去来记录前缀和，从而以O(logn)的复杂度完成每次查询
#in
展开全文
#include <bits/stdc++.h>
#define LCHILD(p) (((p)<<1)|1)
#define RCHILD(P) (((p)+1)<<1)
#define int long long
using namespace std;
vo
展开全文
#include "stdio.h"
#define N 100000
int main(){
long long int n,q,l,r,i,a[N],sum[N],node[N],j;
scanf("%lld %lld",&n,&q);
for(i=0;i<n;i++){
展开全文
#include <iostream>
#include<vector>
using namespace std;
int main() {
int n=0,q=0;
cin>>n>>q;
vector<int> arr(n,
展开全文
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
vector<long
展开全文
第一想法是利用一个二维数组dp来做备忘录，用dpijdp_{ij}dpij表示数组从i到j的和，最后通过l和r直接返回dp中的值就可以了。
代码如下：
#include<iostream>
#include<vector>
using namespace std;
in
展开全文
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
//开long long 数组防止数据过大
long long sum[N], arr[N];
int main() {
int n = 0, q =
展开全文
1 base玩家的福音a数组表示原来的数据，b[i]表示[0, i]的a数组的和。使用一个循环维护既可那么[l, r]的和就是b[r] - b[l - 1];
#include <bits/stdc++.h>
using namespace std;
int main() {
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
