首页 > 代码库 > POJ 3468 A Simple Problem with Integers（线段树区间修改及查询）
POJ 3468 A Simple Problem with Integers（线段树区间修改及查询）
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 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4Sample Output
455915
线段树区间查询的核心思想是Lazy原则，顾名思义，懒！！
就是当修改某区间的值是，现将修改的值记录下来，暂不修改。
此时如果查询区间与上一个修改区间没有交集，那么对结果也没有影响。我等用到这个修改过的区间的值时，再将它的值向下更新。
而且只用向下更新一层，因为递归时我们是根据区间的位置情况连续向下找左右子节点的，所以只更新一层就行，更新多了没用（如果更新到底，就变成单点更新了，复杂度爆炸）
代码如下：
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 #define M 100005 6 struct segTree 7 { 8 int l,r; 9 long long int sum,add; 10 int mid() 11 { 12 return (l+r)>>1; 13 } 14 }tree[M<<2]; 15 int n,m; 16 void PushUp (int now)//向上更新：当前节点的sum等于其左右儿子的sum的和 17 { 18 tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum; 19 } 20 void buildTree (int now,int l,int r) 21 { 22 tree[now].l=l,tree[now].r=r; 23 tree[now].add=0; 24 if (l==r) 25 { 26 scanf("%lld",&tree[now].sum); 27 return; 28 } 29 int m=tree[now].mid(); 30 buildTree(now<<1,l,m);//递归建树 31 buildTree(now<<1|1,m+1,r); 32 PushUp(now);//向上更新 33 } 34 void PushDown (int now,int m) 35 //向下更新：当前节点的add值需要加到自己左右儿子的add与sum上 36 { 37 if (tree[now].add) 38 { 39 tree[now<<1].add+=tree[now].add; 40 tree[now<<1|1].add+=tree[now].add; 41 tree[now<<1].sum+=tree[now].add*(m-(m>>1)); 42 tree[now<<1|1].sum+=tree[now].add*(m>>1); 43 tree[now].add=0; 44 } 45 } 46 void UpDate (int now,int l,int r,int change) 47 //区间[l,r]需要增加值change，now是当前节点 48 { 49 if (tree[now].l==l&&r==tree[now].r) 50 //如果恰好now代表的区间就是更新的区间，一步更新，暂不向下继续更新到其子节点 ，等用到这个节点再向下更新 51 { 52 tree[now].add+=change; 53 tree[now].sum+=(__int64)change*(r-l+1); 54 return ; 55 } 56 if (tree[now].l==tree[now].r) 57 return;//区间长度为1，return 58 PushDown(now,tree[now].r-tree[now].l+1); 59 //用到了当前节点，当前节点向下更新 60 int m=tree[now].mid(); 61 if (r<=m) 62 //==============|==============tree[now]的区间 63 // ******** 要更新的区间 64 UpDate(now<<1,l,r,change); 65 else if (l>m) 66 //==============|==============tree[now]的区间 67 // ******** 要更新的区间 68 UpDate(now<<1|1,l,r,change); 69 else 70 //==============|==============tree[now]的区间 71 // ************* 要更新的区间 72 { 73 UpDate(now<<1,l,m,change); 74 UpDate(now<<1|1,m+1,r,change); 75 } 76 PushUp(now); 77 } 78 long long int query (int now,int l,int r) 79 { 80 if(l==tree[now].l &&r==tree[now].r) 81 { 82 return tree[now].sum; 83 } 84 PushDown(now,tree[now].r-tree[now].l+1);//用到了当前节点，向下更新 85 int m = tree[now].mid(); 86 long long int res = 0; 87 if(r<=m) 88 //==============|==============tree[now]的区间 89 // ******** 要查询的区间 90 res += query(now<<1,l,r); 91 else if(l > m) 92 //==============|==============tree[now]的区间 93 // ******** 要查询的区间 94 res += query(now<<1|1,l,r); 95 //==============|==============tree[now]的区间 96 // ************* 要更新的区间 97 else 98 { 99 res+=query(now<<1,l,m);100 res+=query(now<<1|1,m+1,r);101 }102 return res;103 }104 int main()105 {106 //freopen("de.txt","r",stdin);107 while (~scanf("%d%d",&n,&m))108 {109 buildTree(1,1,n);110 while (m--)111 {112 char op[5];113 scanf("%s",op);114 int x,y,z;115 if (op[0]==‘Q‘)116 {117 scanf("%d%d",&x,&y);118 printf("%lld\n",query(1,x,y));119 }120 else121 {122 scanf("%d%d%d",&x,&y,&z);123 UpDate(1,x,y,z);124 }125 }126 }127 return 0;128 }
POJ 3468 A Simple Problem with Integers（线段树区间修改及查询）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。