树状数组

一个区间，两种操作：区间求和，单点修改。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 100000 + 1000


int n, a[maxn], C[maxn];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int val)
{
    for (int i = x; i <= n; i += lowbit(i))
        C[i] += val;
}

int sum(int x)
{
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        ans += C[i];
    return ans;
}

int main()
{
    int t;
    scanf("%d", &t);
    for (int ca = 1; ca <= t; ca++)
    {
        scanf("%d", &n);

        memset(C, 0, sizeof(C));

        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            add(i, a[i]);
        }

        printf("Case %d:
", ca);

        char s[10];
        while(~scanf("%s", s) && s[0] != 'E')
        {
            int l, r;
            scanf("%d%d", &l, &r);

            if (s[0] == 'A')
                add(l, r);
            if (s[0] == 'S')
                add(l, -r);
            if (s[0] == 'Q')
                printf("%d
", sum(r) - sum(l-1));
        }
    }

}

HDU - 1754 I Hate It

单点修改，区间求最大值。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 200000 + 1000


int n, m, a[maxn], C[maxn];

int lowbit(int x)
{
    return x & -x;
}

void updata(int x, int val)
{
    a[x] = val;
    for (int i = x; i <= n; i += lowbit(i))
        C[i] = max(C[i], val);
}


int found(int l, int r)
{
    int ans = a[r];
    while(l != r)
    {
        for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r))
            ans = max(ans, C[r]);
        ans = max(ans, a[r]);
    }
    return ans;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        memset(C, 0, sizeof(C));
        memset(a, 0, sizeof(a));

        for (int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &a[i]);
            updata(i, a[i]);
        }

        char c;
        for (int i = 1; i <= m; i++)
        {
            getchar();
            int l, r;
            scanf("%c%d%d", &c, &l, &r);

            if (c == 'U')
                updata(l, r);

            if (c == 'Q')
                printf("%d
", found(l, r));
        }
    }

}