首页 > 代码库 > POJ3468-A Simple Problem with Integers(区间更新 + SegmentTree || SplayTree || BinaryIndexTree)
POJ3468-A Simple Problem with Integers(区间更新 + SegmentTree || SplayTree || BinaryIndexTree)
Description
You have N integers, 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 numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands 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
Hint
The sums may exceed the range of 32-bit integers.
Means:
给你一段数列,有区间查询跟区间更新操作
Solve:
果Segment Tree || Binary Index Tree || Splay Tree
PS:线段树更新中有一段tree[ls] += (LL)lazy[id] * (mid - l + 1);这是由于更新的是区间,区间每个点都要加上value，所以要乘以区间点数
Code(SegmentTree):
1 #include <cstdio> 2 #include <cstring> 3 #define FOP freopen("in.in" , "r" , stdin) 4 #define FCL freopen("out.out" , "w" , stdout) 5 #define LL long long 6 #define MAXN 100000+10 7 #define CLR(x) memset(x , 0 , sizeof(x)) 8 #define LSON id << 1 , l , mid 9 #define RSON id << 1 | 1 , mid + 1 , r10 #define ROOT 1 , 1 , n11 #define PUSHUP(x) tree[id] = tree[id << 1] + tree[id << 1 | 1]12 LL tree[MAXN << 2] = {0};13 LL data[MAXN] = {0};14 LL lazy[MAXN << 2] = {0};15 int n , q;16 inline void PushDown(int id , int l , int r)17 {18 if(lazy[id])19 {20 int ls = id << 1 , rs = id << 1 | 1 , mid = (l + r) >> 1;21 lazy[ls] += lazy[id];22 lazy[rs] += lazy[id];23 tree[ls] += (LL)lazy[id] * (mid - l + 1);24 tree[rs] += (LL)lazy[id] * (r - mid);25 lazy[id] = 0;26 }27 }28 void Build(int id , int l , int r)29 {30 if(l == r)31 {32 scanf("%lld" , tree + id);33 lazy[id] = 0;34 return ;35 }36 int mid = (l + r) >> 1;37 Build(id << 1 , l , mid);38 Build(id << 1 | 1 , mid + 1 , r);39 PUSHUP(id);40 }41 LL Query(int id , int l , int r , int x , int y)42 {43 if(x <= l && y >= r)44 {45 return tree[id];46 }47 PushDown(id , l , r);48 int mid = (l + r) >> 1;49 LL res = 0;50 if(x <= mid) res += Query(LSON , x , y);51 if(y > mid) res += Query(RSON , x , y);52 PUSHUP(id);53 return res;54 }55 void Update(int id , int l , int r , int x , int y , int z)56 {57 if(x <= l && y >= r)58 {59 lazy[id] += z;60 tree[id] += (LL)(r - l + 1) * z;61 return;62 }63 PushDown(id , l , r);64 int mid = (l + r) >> 1;65 if(x <= mid) Update(LSON , x , y , z);66 if(y > mid) Update(RSON , x , y , z);67 PUSHUP(id);68 }69 int main()70 {71 scanf("%d%d" , &n , &q);72 Build(ROOT);73 char cmd;74 LL a , b , c;75 while(q--)76 {77 scanf(" %c" , &cmd);78 if(cmd == ‘Q‘)79 {80 scanf("%lld%lld" , &a , &b);81 printf("%lld\n" , Query(ROOT , a , b));82 }83 else84 {85 scanf("%lld%lld%lld" , &a , &b , &c);86 Update(ROOT , a , b , c);87 }88 }89 }
POJ3468-A Simple Problem with Integers(区间更新 + SegmentTree || SplayTree || BinaryIndexTree)