P3372 【模板】线段树 1
提交477.53k
通过195.10k
时间限制1.00s
内存限制512.00MB
题目编号P3372
提供者
难度普及+/提高
历史分数暂无
标签
相关讨论
推荐题目
[ 复制 Markdown](javascript:void 0)[ 展开](javascript:void 0)
[ 进入 IDE 模式](javascript:void 0)
题目描述
如题，已知一个数列 {ai}，你需要进行下面两种操作：
- 将某区间每一个数加上 k。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数 n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数 ai，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：
1 x y k：将区间 [x,y] 内每个数加上 k。2 x y：输出区间 [x,y] 内每个数的和。
输出格式
输出包含若干行整数，即为所有操作 2 的结果。
输入输出样例
输入 #1
5 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4
输出 #1
11 8 20
说明/提示
对于 15% 的数据：n≤8，m≤10。
对于 35% 的数据：n≤103，m≤104。
对于 100% 的数据：1≤n,m≤105，ai,k 为正数，且任意时刻数列的和不超过 2×1018。
【样例解释】
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int n,m;
ll a[N];
ll c[N];
int lowbit(int x){
return x&(-x);
}
void add(int x,int d){
while(x<=n){
c[x]+=d;
x+=lowbit(x);
}
}
int sum(int x){
int v=0;
while(x){
v+=c[x];
x-=lowbit(x);
}
return v;
}
ll cz,x,y,k;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
while(m--){
scanf("%lld%lld%lld",&cz,&x,&y);
if(cz==1){
scanf("%lld",&k);
for(int i=x;i<=y;i++){
add(x,k);
}
}
else{
cout<<sum(y)-sum(x-1)<<endl;
}
}
return 0;
}
/*
*/