單點更新是最最基礎的線段樹，只更新葉子節點，然后把信息用pushup這個函數更新上來。

http://acm.hdu.edu.cn/showproblem.php?pid=1166

update單點更新，query區域求和。

#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #define N 200001 using namespace std; struct node {int l,r;__int64 w; } q[4*N]; void pushup(int rt) {q[rt].w=q[rt*2].w+q[rt*2+1].w; } void build(int l,int r,int rt) {q[rt].l=l;q[rt].r=r;q[rt].w=0;if(l==r){scanf("%I64d",&q[rt].w);return ;}build(l,(l+r)/2,rt*2);build((l+r)/2+1,r,rt*2+1);pushup(rt); } void update(int sum,int key,int l,int r,int rt) {if(sum<l||sum>r)return ;if(l==r&&sum==l){q[rt].w+=(__int64)key;return ;}update(sum,key,l,(l+r)/2,rt*2);update(sum,key,(l+r)/2+1,r,rt*2+1);pushup(rt); } __int64 query(int ll,int rr,int l,int r,int rt) {if(ll>r||rr<l) return 0;if(ll<=l&&rr>=r){return q[rt].w;}return query(ll,rr,l,(l+r)/2,rt*2)+query(ll,rr,(l+r)/2+1,r,rt*2+1); } int main() {int n,sum1,sum2,T,K=0;char a[10];scanf("%d",&T);while(T--){K++;scanf("%d",&n);build(1,n,1);printf("Case %d:\n",K);while(scanf("%s",a)!=EOF){if(strcmp(a,"End")==0) break;else if(strcmp(a,"Query")==0){scanf("%d%d",&sum1,&sum2);__int64 t=query(sum1,sum2,1,n,1);printf("%I64d\n",t);}else if(strcmp(a,"Sub")==0){scanf("%d%d",&sum1,&sum2);update(sum1,-sum2,1,n,1);}else if(strcmp(a,"Add")==0){scanf("%d%d",&sum1,&sum2);update(sum1,sum2,1,n,1);}}}return 0; }

?

?

http://acm.hdu.edu.cn/showproblem.php?pid=1754

update單點替換，query區間最值

#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #define N 200001 using namespace std; struct node {int l,r;__int64 w; }q[4*N]; void pushup(int rt) {q[rt].w=max(q[rt*2].w,q[rt*2+1].w); } void build(int l,int r,int rt) {q[rt].l=l;q[rt].r=r;q[rt].w=0;if(l==r){scanf("%I64d",&q[rt].w);return ;}build(l,(l+r)/2,rt*2);build((l+r)/2+1,r,rt*2+1);pushup(rt); } void update(int sum,int key,int l,int r,int rt) {if(sum<l||sum>r)return ;if(l==r&&sum==l){q[rt].w=(__int64)key;return ;}update(sum,key,l,(l+r)/2,rt*2);update(sum,key,(l+r)/2+1,r,rt*2+1);pushup(rt); } __int64 query(int ll,int rr,int l,int r,int rt) {if(ll>r||rr<l) return 0;if(ll<=l&&rr>=r){return q[rt].w;}return max(query(ll,rr,l,(l+r)/2,rt*2),query(ll,rr,(l+r)/2+1,r,rt*2+1)); } int main() {int n,m,sum1,sum2;char a[3];while(scanf("%d%d",&n,&m)!=EOF){build(1,n,1);while(m--){scanf("%s%d%d",a,&sum1,&sum2);if(a[0]=='U'){update(sum1,sum2,1,n,1);}else if(a[0]=='Q'){__int64 t=query(sum1,sum2,1,n,1);printf("%I64d\n",t);}}}return 0; }

?

轉載于:https://www.cnblogs.com/zhangmingcheng/p/3902525.html

總結

以上是生活随笔為你收集整理的hdu1166敌兵布阵hdu1754I Hate It(线段树入门）的全部內容，希望文章能夠幫你解決所遇到的問題。

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