【线段树】模板-HDU-1166-点改区查

本文主要是介绍【线段树】模板-HDU-1166-点改区查，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

存个线段树模板，已经用过好多次了，好用的

【来自hh大神的模板】

例题链接： HDU-1166-敌兵布阵

#include <cstdio>
#include <iostream>
using namespace std;#define lson l, m ,rt<<1
#define rson m+1, r, rt<<1|1
const int maxn = 50050;
int 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);else update(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()
{freopen("input.txt","r",stdin);int T,n,cc=1;cin>>T;while(T--){printf("Case %d:\n",cc);cc++;scanf("%d",&n);build(1,n,1);char op[10];while(scanf("%s",op)){if(op[0] == 'E')break;int a,b;scanf("%d%d",&a,&b);switch(op[0]){case 'A': update(a,b,1,n,1);break;case 'S': update(a,-b,1,n,1);break;case 'Q': printf("%d\n",query(a,b,1,n,1));break;}}}return 0;
}

这篇关于【线段树】模板-HDU-1166-点改区查的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---