HDU 1166(线段树；树状数组)

分手后的思念是犯贱 2022-09-20 11:22 185阅读 0赞

题意：如题。

树状数组：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int a[50009];
    
    int lowbit(int n)
    {
        return n&-n;
    }
    
    int sum(int end)
    {
        int s = 0;
        while (end > 0)
        {
            s += a[end];
            end -= lowbit(end);
        }
        return s;
    }
    
    void plus(int pos, int num, int up)
    {
        while (pos <= up)
        {
            a[pos] += num;
            pos += lowbit(pos);
        }
    }
    
    int main()
    {
        int T, N, i, n, m, t = 0;
        char s[20];
        scanf("%d", &T);
        while (T--)
        {
            printf("Case %d:\n", ++t);
            scanf("%d", &N);
            memset(a+1, 0, sizeof(int) * N);
            for (i = 1; i <= N; ++i)
            {
                scanf("%d", &n);
                plus(i, n, N);
            }
            while (scanf("%s", s), s[0] != 'E')
            {
                scanf("%d%d", &n, &m);
                if (s[0] == 'Q')
                    printf("%d\n", sum(m) - sum(n-1));
                else if (s[0] == 'A')
                {
                    plus(n, m, N);
                }
                else plus(n, -m, N);
            }
        }
    }

线段树:

#include <cstdio>
    #include <cstring>
    
    const int maxn = 50009;
    
    int sum[maxn<<2];
    
    void pushUP(int rt)
    {
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    }
    
    void build(int l, int r, int rt)
    {
        if (l == r)
        {
            scanf("%d", sum+rt);
            return;
        }
        int m = (l+r) >> 1;
        build(l, m, rt<<1);
        build(m+1, r, rt<<1|1);
        pushUP(rt);
    }
    
    void update(int p, int add, int l, int r, int rt)
    {
        if (l == r)
        {
            sum[rt] += add;
            return;
        }
        int m = (l+r) >> 1;
        if (p <= m) update(p, add, l, m, rt<<1);
        else update(p, add, m+1, r, rt<<1|1);
        pushUP(rt);
    }
    
    int query(int L, int R, int l, int r, int rt)
    {
        if (L <= l && r <= R)
            return sum[rt];
        int m = (l + r) >> 1;
        int ret = 0;
        if (L <= m) ret += query(L, R, l, m, rt<<1);
        if (R > m) ret += query(L, R, m+1, r, rt<<1|1);
        return ret;
    }
    
    int main()
    {
        int T, n;
        scanf("%d", &T);
        for (int cas = 1; cas <= T; ++cas)
        {
            printf("Case %d:\n", cas);
            scanf("%d", &n);
            build(1, n, 1);
            char op[10];
            while (scanf("%s", op))
            {
                if (op[0] == 'E') break;
                int a, b;
                scanf("%d%d", &a, &b);
                if (op[0] == 'Q')
                    printf("%d\n", query(a, b, 1, n, 1));
                else if (op[0] == 'S')
                    update(a, -b, 1, n, 1);
                else update(a, b, 1, n, 1);
            }
        }
        return 0;
    }