HDU - 1166 敌兵布阵

题意：省略

思路：经典的线段树更新节点

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
const int MAXN = 50010;

struct Node{
    int left,right;
    int sum;
}node[MAXN*4];
int n,num[MAXN];

void init(int left,int right,int pos){
    node[pos].left = left;
    node[pos].right = right;
    if (left == right){
        node[pos].sum = num[left];
        return;
    }
    int x = (left+right) >> 1;
    init(left,x,pos<<1);
    init(x+1,right,pos<<1|1);
    node[pos].sum = node[pos<<1].sum + node[pos<<1|1].sum;
}

void update(int index,int val,int pos){
    if (node[pos].left == node[pos].right){
        node[pos].sum += val;
        return;
    }
    int x = (node[pos].left+node[pos].right) >> 1;
    if (index <= x)
        update(index,val,pos<<1);
    else update(index,val,pos<<1|1);
    node[pos].sum = node[pos<<1].sum + node[pos<<1|1].sum;
}

int query(int left,int right,int pos){
    if (node[pos].left == left && node[pos].right == right)
        return node[pos].sum;
    int x = (node[pos].left+node[pos].right) >> 1;
    if (right <= x)
        return query(left,right,pos<<1);
    else if (left > x)
        return query(left,right,pos<<1|1);
    else return query(left,x,pos<<1)+query(x+1,right,pos<<1|1);
}

void input(){
    char str[N];
    scanf("%d",&n);
    for (int i = 1; i <= n; i++)
        scanf("%d",&num[i]);
    init(1,n,1);
    getchar();
    int x,y;
    while (scanf("%s",str) != EOF && str[0] != ‘E‘){
        scanf("%d%d%*c",&x,&y);
        if (str[0] == ‘Q‘)
            printf("%d\n",query(x,y,1));
        else if (str[0] == ‘A‘)
            update(x,y,1);
        else update(x,-y,1);
    }
}

int main(){
    int t,cas = 1;
    scanf("%d",&t);
    while (t--){
        printf("Case %d:\n",cas++);
        input();
    }
    return 0;
}

HDU - 1166 敌兵布阵

原文：http://blog.csdn.net/u011345136/article/details/19507609