題目1：敵兵布陣?

?

線段樹的主要操作：（1）建立線段樹（Build）???????? ?（2）更新區(qū)間值?（Update）???????????（3）查詢區(qū)間（Query）

寫法一：

#include <stdio.h> #define maxn 55555#define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1int sum[maxn<<2];void PushUP(int rt) {sum[rt]=sum[rt<<1]+sum[rt<<1|1]; }void Build(int l,int r,int rt) {if(l==r){scanf("%d",&sum[rt]);return;}int m=(l+r)>>1;Build(lson);Build(rson);PushUP(rt); }void Update(int p,int add,int l,int r,int rt) {if(l==r){sum[rt]+=add;return;}int m=(l+r)>>1;if(p<=m)Update(p,add,lson);elseUpdate(p,add,rson);PushUP(rt); }int Query(int L,int R,int l,int r,int rt) {if(L<=l&&R>=r)return sum[rt];int m=(l+r)>>1;int ret=0;if(L<=m) ret+=Query(L,R,lson);if(R>m) ret+=Query(L,R,rson);return ret; }int main() {int n,t,k=1;char s[15];scanf("%d",&t);while(t--){printf("Case %d:\n",k++);scanf("%d",&n);Build(1,n,1);while(~scanf("%s",s)){if(s[0]=='E')break;int a,b;scanf("%d%d",&a,&b);if(s[0]=='Q')printf("%d\n",Query(a,b,1,n,1));else if(s[0]=='S')Update(a,-b,1,n,1);elseUpdate(a,b,1,n,1);}}return 0; }

?

寫法二：

#include<stdio.h> #define N 50005typedef struct {int Lson;int Rson;int sum; }Tree;Tree seg_tree[N*3]; int a[N];void Build(int num,int L,int R) {seg_tree[num].Lson=L;seg_tree[num].Rson=R;if(L==R){seg_tree[num].sum=a[L];return;}else{int mid=(L+R)>>1;Build(2*num,L,mid);Build(2*num+1,mid+1,R);seg_tree[num].sum=seg_tree[2*num].sum+seg_tree[2*num+1].sum;} }void Update(int num,int L,int R,int a,int b) {seg_tree[num].sum+=b;if(L==R&&L==a)return;int mid=(L+R)>>1;if(a<=mid)Update(2*num,L,mid,a,b);elseUpdate(2*num+1,mid+1,R,a,b); }int Query(int num,int L,int R,int a,int b) {if(L==a&&R==b)return seg_tree[num].sum;int mid=(L+R)>>1;if(b<=mid)return Query(2*num,L,mid,a,b);if(a>=mid+1)return Query(2*num+1,mid+1,R,a,b);return Query(2*num,L,mid,a,mid)+Query(2*num+1,mid+1,R,mid+1,b); }int main() {int t,n,k;char str[15];scanf("%d",&t);for(k=1;k<=t;k++){printf("Case %d:\n",k);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);Build(1,1,n);while(~scanf("%s",str)){int a,b;if(str[0]=='E')break;scanf("%d%d",&a,&b);if(str[0]=='A')Update(1,1,n,a,b);else if(str[0]=='S')Update(1,1,n,a,-b);elseprintf("%d\n",Query(1,1,n,a,b));}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的线段树求区间和(单点更新)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。