首页 > 代码库 > UVA 2191 Potentiometers

UVA 2191 Potentiometers

题意很简单:就是输入先n个数字,然后进行一系列操作!

           S num sum 就是将第num个数字的值改成sum;

           M a b 就是求从位置a到位置b的数字的和!


这个题基本就是一个裸的树状数组,直接使用树状数组,然后根据题意打出对应的代码即可!再注意一下细节应该就能AC了!!!


代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>//UVA 2191 Potentiometers
using namespace std;
const int maxn=1000000;
int c[maxn];
int ss[maxn];
int n;
int lowbit(int x)
{
    return x&(-x);
}
int sum(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void update(int x,int d)
{
    while(x<=n)
    {
        c[x]+=d;
        x+=lowbit(x);
    }
}
int main()
{
    int ji=1;
    while(cin>>n)
    {
        memset(c,0,sizeof(c));
        if(!n)
            break;
        for(int i=1; i<=n; i++)
        {
            cin>>ss[i];
            update(i,ss[i]);
        }
        char s[10];
        int a,b;
        if(ji!=1)
            cout<<endl;
        printf("Case %d:\n",ji++);
        while(cin>>s)
        {
            if(!strcmp(s,"END"))
                break;
            if(s[0]=='S')
            {
                cin>>a>>b;
                update(a,b-ss[a]);
                ss[a]=b;
            }
            if(s[0]=='M')
            {
                cin>>a>>b;
                cout<<sum(b)-sum(a-1)<<endl;
            }
        }
    }
    return 0;
}


UVA 2191 Potentiometers