可参考这个题
http://blog.csdn.net/gaotong2055/article/details/9300141
Description
You haveNintegers,A1,A2, ... ,AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is
to ask for the sum of numbers in a given interval.
Input
The first line contains two numbersNandQ. 1 ≤N,Q≤ 100000.
The second line containsNnumbers, the initial values ofA1,A2, ... ,AN. -1000000000 ≤Ai≤ 1000000000.
Each of the nextQlines represents an operation.
"Cabc" means addingcto each ofAa,Aa+1, ... ,Ab. -10000 ≤c≤ 10000.
"Qab" means querying the sum ofAa,Aa+1, ... ,Ab.
Output
You need to answer allQcommands in order. One answer in a line.
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15
#include <iostream>
#include <stdio.h>
using namespace std;
int n,q;
long long tree[400000];
long long add[400000];
int a,b,c;
void build(int l, int r, int k){
add[k] = 0;
if(l==r){
scanf("%lld", &tree[k]);
return;
}
int m = (l+r)/2;
build( l, m, 2*k);
build( m+1, r, 2*k + 1);
tree[k] = tree[2*k] + tree[2*k+1];
}
void down(int k,int m){
if(add[k]){
add[k*2+1] += add[k];
add[k*2] += add[k];
tree[k*2] += (m-m/2) * add[k];
tree[k*2+1] += (m/2) * add[k];
add[k] = 0;
}
}
void update(int l,int r, int k){
if( a <= l && b >= r){ //找到合适的区间
add[k] += c;
tree[k] += (long long)(r - l + 1) * c;
return;
}
down(k, r-l+1); //更新子树
int m = (l+r)/2;
if(a <= m) update(l, m, 2*k);
if(b > m) update(m+1, r, 2*k+1);
tree[k] = tree[2*k] + tree[2*k+1];
}
long long query(int l, int r, int k){
if(a <= l && b >= r)
{
return tree[k];
}
down(k, r-l+1); //查询的时候需要更新子树
long long ans = 0;
int m = (l+r)/2;
if(a <= m)
ans += query(l , m, k*2);
if(b > m)
ans += query(m+1, r, k*2+1);
return ans;
}
int main() {
//freopen("in.txt", "r", stdin);
char cmd[5];
while(scanf("%d %d", &n, &q) != EOF){
build(1, n ,1);
while(q--){
scanf("%s", cmd);
if(cmd[0] == 'Q'){
scanf("%d %d",&a,&b);
printf("%lld\n", query(1,n,1));
}else{
scanf("%d %d %d",&a, &b, &c);
update(1, n, 1);
}
}
}
return 0;
}
分享到:
相关推荐
北大POJ1321-Chess Problem POJ1321-Chess Problem
树状数组解决区间操作_高效 对数组的某个区间进行两种操作:1)求和 2)每个数据加常数。要求:时间复杂度低
POJ3468,线段树处理,注意longlongint
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
poj 2452 Sticks Problem.md
NULL 博文链接:https://128kj.iteye.com/blog/1739064
北大POJ3414-Pots 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2996-Help Me with the Game 解题报告+AC代码
POJ2601 solution 题解 递推 POJ2601
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
poj 3757 Simple Distributed storage system.md
poj的结题报告,里面有一些详细的说明。poj的结题报告,里面有一些详细的说明
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同...poj 3468 成段更新 ural 1019 覆盖加统计最长同一个颜色 zoj 2301 和上一题差不多,但是这个染色染的是点,注意染色为空的状况
北大POJ1942-Paths on a Grid 解题报告+AC代码
在进行ACM编程训练时做字符串专题的一些题目(POJ1782,POJ1790,POJ1951,POJ2003,POJ2121)
北大POJ2488-A Knight's Journey 解题报告+AC代码
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
poj分类poj分类poj分类poj分类