首页 > 代码库 > 【POJ】A Simple Problem with Integers（线段树区间修增减求和）
【POJ】A Simple Problem with Integers（线段树区间修增减求和）
线段树区间修改增加问题，模板题，注意懒惰处理。
| 13443449 | 201301052100 | 3468 | Accepted | 4308K | 1610MS | C++ | 2362B | 2014-09-15 15:46:35 |
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<cstdlib>
#include<stack>
#include<set>
#include<string>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define esp 1e-10
const int maxn = 100000 + 10;
#define MAXD 100
int n , m;
LL tree[maxn << 2];
LL mark[maxn << 2];
void BuildTree(int L,int R,int pos){
if(L == R){
scanf("%I64d",&tree[pos]);
return ;
}
int m = (L + R) >> 1;
BuildTree(L, m , pos << 1);
BuildTree(m + 1, R , (pos << 1)|1);
tree[pos] = tree[pos << 1] + tree[(pos << 1)|1];
return ;
}
void UpDate(int l,int r,int add,int L,int R,int pos){
if(l <= L && R <= r){
mark[pos] += add;
tree[pos] += add * (R - L + 1);
return ;
}
int m = (L + R) >> 1;
int len = R - L + 1;
if(mark[pos]){ //懒惰标记下移
mark[pos << 1] += mark[pos];
mark[(pos << 1)|1] += mark[pos];
tree[pos << 1] += mark[pos] * (len - (len >> 1));
tree[(pos << 1)|1] += mark[pos] * (len >> 1);
mark[pos] = 0;
}
if(l <= m) UpDate(l,r,add,L,m,pos << 1);
if(r > m) UpDate(l,r,add,m + 1,R,(pos << 1)|1);
tree[pos] = tree[pos << 1] + tree[(pos << 1)|1];
return ;
}
LL Query(int l,int r,int L,int R,int pos){
if(l <= L && R <= r){
return tree[pos];
}
int m = (L + R) >> 1;
int len = R - L + 1;
if(mark[pos]){ //懒惰标记下移
mark[pos << 1] += mark[pos];
mark[(pos << 1)|1] += mark[pos];
tree[pos << 1] += mark[pos] * (len - (len >> 1));
tree[(pos << 1)|1] += mark[pos] * (len >> 1);
mark[pos] = 0;
}
LL ret = 0;
if(l <= m) ret += Query(l,r,L,m,pos << 1);
if(r > m) ret += Query(l,r,m + 1,R,(pos << 1)|1);
return ret;
}
int main(){
char str[MAXD];
scanf("%d%d",&n,&m);
BuildTree(1,n,1);
for(int i = 0 ; i < m ; i++){
scanf("%s",str);
if(str[0] == 'Q'){
int x ,y;
scanf("%d%d",&x,&y);
LL ans = Query(x,y,1,n,1);
printf("%I64d\n",ans);
}
else if(str[0] == 'C'){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
UpDate(x,y,z,1,n,1);
}
}
return 0;
}
【POJ】A Simple Problem with Integers（线段树区间修增减求和）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。