[hdu]1166敌兵布阵-线段树&树状数组

简单题，建树、修改、求和。练手的！

树状数组：

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define MAX 50001 int c[MAX],a[MAX],n;//c为树状数组，a为原数组，n为输入个数 int getsum(int i){ //求a[1]…a[i]的和,如果想要a[j]…a[k]则getsum(k)-getsum(i) int res; for(res=0;i>0;i-=i&(-i)) res+=c[i]; return res; } void modify(int i,int m){//将第i个元素加m for(;i<=MAX;i+=i&(-i)) c[i]+=m; } char ord[10] ; int main (){ //freopen ("*.txt", "r", stdin) ; //freopen ("*.out", "w", stdout) ; int T, i, j, no = 1 ; scanf("%d", &T) ; while (T --) { scanf("%d", &n); memset (c, 0, sizeof(c[0]) * (n + 1)) ; for (i = 1; i <= n; ++ i) { scanf("%d", &a[i]); modify(i, a[i]) ; } printf("Case %d:/n", no ++); while(scanf("%s", ord), ord[0] != 'E') { scanf("%d%d", &i, &j); if(ord[0] == 'Q') { printf("%d/n", getsum(j) - getsum(i-1)); } if(ord[0] == 'A') { modify(i, j) ; } if(ord[0] == 'S') { modify(i, -j) ; } } } //system ("pause") ; return 0 ; } 

线段树：

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define size 50001 struct xds { int a, b ; int lson, rson ; int info ; }tree[size*3] ; int tot ; void make_xds(int s, int t) { int now = ++tot ; tree[now].a = s ; tree[now].b = t ; tree[now].info = 0 ; if(t - s > 0)//到单个结点 { int mid = (s + t) >> 1 ; tree[now].lson = tot + 1 ; make_xds(s, mid) ; tree[now].rson = tot + 1 ; make_xds(mid + 1, t) ; } else tree[now].lson = tree[now].rson = 0 ; } void update(int p, int s, int t, int info) { tree[p].info += info ; if(tree[p].a == tree[p].b) return ; int mid = (tree[p].a + tree[p].b) >> 1 ; if(s <= mid) update(tree[p].lson, s, t, info) ; if(t > mid) update(tree[p].rson, s, t, info) ; } int query(int p, int s, int t) { if(tree[p].a == s && tree[p].b == t) { return tree[p].info ; } int mid = (tree[p].a + tree[p].b) >> 1 ; if(t <= mid) return query(tree[p].lson, s, t) ; else if(s > mid) return query(tree[p].rson, s, t) ; else return query(tree[p].lson, s, mid) + query(tree[p].rson, mid + 1, t) ; } int main (){ int T, i, j, N, no = 1 ; char ord[10] ; scanf("%d", &T); while( T -- ) { scanf("%d", &N); tot = 0 ; make_xds(1, N) ; for (i = 1; i <= N; i ++) { scanf("%d", &j); update(1, i, i, j) ; //system("pause"); } printf("Case %d:/n", no++); while(scanf("%s", ord)) { if(ord[0] == 'E') break ; scanf("%d%d", &i, &j); switch (ord[0]) { case 'Q': printf("%d/n", query(1, i, j)); break ; case 'A': update(1, i, i, j) ; break ; case 'S': update(1, i, i, -j) ; } } } //system ("pause") ; return 0 ; } 

最后

以上就是醉熏小甜瓜最近收集整理的关于[hdu]1166敌兵布阵-线段树&树状数组的全部内容，更多相关[hdu]1166敌兵布阵-线段树&树状数组内容请搜索靠谱客的其他文章。