題目鏈接:? http://poj.org/problem?id=3468

題目大意:? 給出N個數，和M次查詢

?????????????????C a b c? 區間[a,b]的值都加上c

???????????????? Q a b???? 查詢區間[a,b]值的和

解題思路:? 線段樹區間lazy延遲更新，每次插入區間標記lazy

???????????????? 下次再操作此區間時用lazy更新下面的子樹

???????????????? ?每個結點存儲值是區間的和

?????????????? ?? 更新和查詢的時間復雜度都是O(logN)

代碼:

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 201000 #define MID(a,b) (a+b)>>1 #define L(a) a<<1 #define R(a) (a<<1|1) typedef struct{int left,right;long long int sum,add; }Node;Node Tree[MAX<<2]={0}; long long int num[MAX];void Build(long long int t,int l,int r) //以1為根節點建立線段樹[l,r] {Tree[t].left=l,Tree[t].right=r;if(Tree[t].left==Tree[t].right){Tree[t].sum=num[Tree[t].right];Tree[t].add=0;return ;}int mid=MID(Tree[t].left,Tree[t].right);Build(L(t),l,mid);Build(R(t),mid+1,r);Tree[t].sum=Tree[L(t)].sum+Tree[R(t)].sum; }void Insert(long long int t,int l,int r,long long int m) //向區間[l,r]插入m {if(Tree[t].left==l&&Tree[t].right==r){Tree[t].sum+=(Tree[t].right-Tree[t].left+1)*m;Tree[t].add+=m;return ;}if(Tree[t].add!=0) //無論是插入還是查詢都要更新lazy{Tree[L(t)].sum+=(Tree[L(t)].right-Tree[L(t)].left+1)*Tree[t].add;Tree[R(t)].sum+=(Tree[R(t)].right-Tree[R(t)].left+1)*Tree[t].add;Tree[L(t)].add+=Tree[t].add;Tree[R(t)].add+=Tree[t].add;Tree[t].add=0;}int mid=MID(Tree[t].left,Tree[t].right);if(l>mid){Insert(R(t),l,r,m);}else if(r<=mid){Insert(L(t),l,r,m);}else{Insert(L(t),l,mid,m);Insert(R(t),mid+1,r,m);}Tree[t].sum=Tree[L(t)].sum+Tree[R(t)].sum; }long long int Query(long long int t,int l,int r) //查詢區間[a,b] {if(Tree[t].left==l&&Tree[t].right==r){return Tree[t].sum;}if(Tree[t].add!=0) //lazy更新{Tree[L(t)].sum+=(Tree[L(t)].right-Tree[L(t)].left+1)*Tree[t].add;Tree[R(t)].sum+=(Tree[R(t)].right-Tree[R(t)].left+1)*Tree[t].add;Tree[L(t)].add+=Tree[t].add;Tree[R(t)].add+=Tree[t].add;Tree[t].add=0;}int mid=MID(Tree[t].left,Tree[t].right);if(l>mid){return Query(R(t),l,r);}else if(r<=mid){return Query(L(t),l,r);}else{return Query(L(t),l,mid)+Query(R(t),mid+1,r);}Tree[t].sum=Tree[L(t)].sum+Tree[R(t)].sum; //更新結點: 結點的值=左子樹+右子樹 }int main() {char ch;int n,a,b,c;long long int i,m;scanf("%d%lld",&n,&m);for(i=1;i<=n;i++) //初始化輸入scanf("%lld",&num[i]);Build(1,1,n);for(i=1;i<=m;i++){getchar();scanf("%c",&ch);if(ch=='C'){scanf("%d%d%d",&a,&b,&c);Insert(1,a,b,c); //區間[a,b]都加上c}else{scanf("%d%d",&a,&b);printf("%lld\n",Query(1,a,b)); //查詢區間[a,b]的和}}return 0; }

注：原創文章，轉載請注明出處

?

總結

以上是生活随笔為你收集整理的poj 3468 A Simple Problem with Integers(线段树区区)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。