UVALive 2191 Potentiometers （树状数组）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=192

给你一个长度为n的数组A，有两种操作，操作一：(S x y) 将A[x]的大小置为y，操作二：(M x y) 求A[x], A[x+1] ... A[y］的和

用一个额外的数组tmp存储数组A，然后将 S x y转换为树状数组的 add x y-tmp[x]

#include <iostream>

#include <cstdio>

#include <cstring>

#define maxn 200010

using namespace std;

typedef long long LL;

LL c[maxn];

int n, arr[maxn];

int lowbit(int x);

void add(int x, int u);

LL sum(int x);

int main(void)

{

    int ca = ;

    while (scanf("%d", &n), n)

    {

        memset( c, , sizeof(c));

        int x, y;

        char ope[];

        for (int i = ; i <= n; ++i)

        {

            scanf("%d", arr + i);

            add( i, arr[i]);

        }

        if (ca)

            putchar();

        printf("Case %d:\n", ++ca);

        while (scanf("%s", ope), ope[] != 'E')

        {

            scanf("%d %d", &x, &y);

            if (ope[] == 'S')

            {

                add( x, y - arr[x]);

                arr[x] = y;

            }

            else

            {

                printf("%lld\n", sum(y) - sum(x - ));

            }

        }

    }

    return ;

}

int lowbit(int x)

{

    return x&(-x);

}

LL sum(int x)

{

    LL result = ;

    while (x > )

    {

        result += c[x];

        x -= lowbit(x);

    }

    return result;

}

void add(int x, int u)

{

    while (x <= n)

    {

        c[x] += u;

        x += lowbit(x);

    }

}