UVALive - 2191 Potentiometers

题意：S操作将x改为y，M操作求[x,y]的和

思路：稍加改动一下树状数组就行了，当然线段树也可以

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 400005;

int n,t[MAXN];

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

void Update(int x,int d){
    while (x <= n)
        t[x] += d,x += lowbit(x);
}

long long sum(int x){
    int ret = 0;
    while (x > 0)
        ret += t[x],x -= lowbit(x);
    return ret;
}

int main(){
    int cas = 1;
    while (scanf("%d",&n) != EOF && n){
        memset(t,0,sizeof(t));
        for (int i = 1; i <= n; i++){
            int x;
            scanf("%d",&x);
            Update(i,x);
        }
        if (cas > 1)
            printf("\n");
        printf("Case %d:\n",cas++);
        while (1){
            char op[10];
            scanf("%s",op);
            if (op[0] == ‘E‘)
                break;
            if (op[0] == ‘S‘){
                int x,y;
                scanf("%d%d",&x,&y);
                long long ans = sum(x) - sum(x-1);
                Update(x,y-ans);
            }
            else {
                int x,y;
                scanf("%d%d",&x,&y);
                printf("%lld\n",sum(y)-sum(x-1));
            }
        }
    }
    return 0;
}

UVALive - 2191 Potentiometers

原文：http://blog.csdn.net/u011345136/article/details/19765651