HDU-1166 敌兵布阵（树状数组做法、线段树做法）

树状数组做法：
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
using namespace std;
typedef long long ll;

int a[50005]; //原数组
int c[50005]; //树状数组

void init() //初始化a,c数组
{
    memset(a, 0, sizeof(a));
    memset(c, 0, sizeof(c));
}

int n; //一共多少个兵营

int lowbit(int x)
{
    return x&(-x);
//x&(-x)，
//x为0时，结果为0；
//x为奇数时，结果为1；
//x为偶数时，结果为x中2的最大次方的因子。
}

void updata(int i,int k) //在i位置加上k，并更新数组的数据
{
    while(i<=n)
    {
        c[i]+=k;
        i+=lowbit(i);
    }
}

int getsum(int i) //求前i项的和
{
    int ans=0;
    while(i>0)
    {
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}

int main()
{
    int t;
    cin >> t;
    for (int I=1;I<=t;I++)
    {
        cout << "Case " << I << ":" << endl;
        init();

        cin >> n;
        for (int i=1;i<=n;i++)
        {
            cin >> a[i];
            updata(i,a[i]);
        }

        string s;
        int x,y;
        while(cin >> s)
        {
            if(s=="End") break;
            cin >> x >> y;
            if(s=="Sub") updata(x, -y);
            else if(s=="Add") updata(x, y);
            else
            {
                int sum = getsum(y) - getsum(x-1);
                cout << sum << endl;
            }
        }
    }
}

线段树做法：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
const int maxn = 50005;
int T,n;
int a[maxn];
string s;
struct sss
{
    int val;
}SegTree[maxn<<2];

void build(int l,int r,int rt)
{
    if(l==r)
    {
        SegTree[rt].val = a[l];
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    SegTree[rt].val = SegTree[rt<<1].val + SegTree[rt<<1|1].val; //回溯方法
}

void update(int L,int C,int l,int r,int rt)
{
    if(l==r)
    {
        SegTree[rt].val += C;  //这里是rt的val+=C,不是l或r的
        return;
    }
    int mid = (l+r) >> 1 ;
    if(L <= mid) update(L, C, l, mid, rt<<1);
    else         update(L, C, mid+1, r, rt<<1|1);
    SegTree[rt].val = SegTree[rt<<1].val + SegTree[rt<<1|1].val;
}

int query(int L,int R,int l,int r,int rt)
{
    if(l>=L && r<=R) return SegTree[rt].val;
    if(l>R || r<L) return 0;
    int mid = (l+r)>>1;
    return query(L, R, l, mid, rt<<1) + query(L, R, mid+1, r, rt<<1|1);
}


int main()
{
    scanf("%d",&T);
    for (int I=1;I<=T;I++)
    {
        cout << "Case " << I << ":" << endl;
        scanf("%d",&n);
        for (int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        build(1, n, 1); //相当于初始化，不用像树状数组单独初始化了
        while(cin >> s)
        {
            int x,y;
            if(s=="End") break;
            else
            {
                scanf("%d %d",&x,&y);
                if(s=="Add") update(x, y, 1, n, 1);
                if(s=="Sub") update(x, -y, 1, n, 1);
                if(s=="Query") cout << query(x, y, 1, n, 1) << endl;
            }
        }
    }
    return 0;
}