【樹狀數組】HDU 1166 敵兵布陣

HDU 1166 敵兵布陣

題意：單點修改，區間查詢

思路：樹狀數組模闆題

思考：！！比線段樹寫的簡短得多，但是忘了初始化樹狀數組QAQ……

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <list>
#include <map>
#define INF 0x3f3f3f3f
#define P(x) x>0 ? x : 0
#define MID l + r >> 1
#define lsn rt << 1
#define rsn rt << 1 | 1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define lowbit(x) x & (-x)

using namespace std;
typedef long long ll;
typedef vector<int>:: iterator VITer;
const int maxN=5e4+5;
int N;
int num[maxN];
int C[maxN];

void add(int i, int val)
{
    while(i <= N)
    {
        C[i] += val ;
        i += lowbit(i);
    }
}

int getsum(int i)
{
    int res = 0;
    while(i > 0)
    {
        res += C[i];
        i -= lowbit(i);
    }
    return res;
}

void init() { memset(C, 0, sizeof(C)); }

int main()
{
    int T;
    scanf("%d", &T);
    for(int Case = 1; Case <= T ; Case++)
    {
        init();
        scanf("%d", &N);
        for(int i=1; i<=N ; i++)
        {
            scanf("%d", &num[i]);
            add(i, num[i]);
        }
        printf("Case %d:\n", Case);
        char s[10];
        while(~scanf("%s", s))
        {
            if(s[0] == 'E')
                break;
            int a,b; scanf("%d%d", &a, &b);
            if( s[0 ]== 'A' )
            {
                num[a] += b;
                add(a, b);
            }
            else if(s[0] == 'S')
            {
                if(num[a] < b)
                    b = num[a];
                num[a] = P(num[a] - b);
                add(a, -b);
            }
            else if(s[0] == 'Q')
                printf("%d\n", getsum(b)-getsum(a-1));
        }
    }
    return 0;
}