标题：uva - 2191 - Potentiometers
出处：Felix021
时间：Sun, 08 Mar 2009 01:32:09 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1495

内容：
抽象题意：给出最多200,000个不超过1000的非负整数，对最多200,000次以下两类操作进行处理
1.  M x y   ——求第x到第y个整数之间的所有整数的和。
2.  S x v   ——将第x个整数的值置为v。

显然，硬搞要TLE的，稍微想了一下，就知道应该用线段树(或者树状数组?)来完成。
关于线段树可以参考 http://acm.whu.edu.cn/blog/read.php?26 以及 http://acm.whu.edu.cn/blog/read.php?51

简单的说，就是用一个平衡二叉树来存储这些东西，
每个叶节点存放一个整数(一个单位"线段")，
而每个分支节点存放的是一条"线段"

在M操作的时候，只要递归地将线段xy分割，能够在logN的时间内查询出
在S操作的时候，只要递归地找到对应的叶节点更新，并在返回的时候一层层更新涉及到的分支节点即可，也是logN。

好久没有写稍长的代码了，这个线段树的具体实现也忘得差不多了，还是去翻了一下yyt的论文。
不过这次写得顺利多了，思路比较清晰。
具体的代码为
#include<stdio.h>

struct node{
    int l, m, r, v;
} tree[1000100];
int res[200100];

void make(int l, int r, int i = 1){
    tree[i].l = l;
    tree[i].r = r;
    tree[i].m = (l + r) / 2;
    if(l == r){
        tree[i].v = res[l];
        return;
    }else{
        make(l, tree[i].m, 2 * i);
        make(tree[i].m + 1, r, 2 * i + 1);
        tree[i].v = tree[2*i].v + tree[2*i+1].v;
    }
}

void insert(int n, int v, int i = 1){
    if(tree[i].l == tree[i].r && tree[i].l == n){
        tree[i].v = v;
    }else{
        if(n <= tree[i].m){
            insert(n, v, 2 * i);
        }else{
            insert(n, v, 2 * i + 1);
        }
        tree[i].v = tree[2*i].v + tree[2*i+1].v;
    }
}

int count(int l, int r, int i = 1){
    if(tree[i].l == l && tree[i].r == r){
        return tree[i].v;
    }else{
        if(r <= tree[i].m){
            return count(l, r, 2 * i);
        }else if(l > tree[i].m){
            return count(l, r, 2 * i + 1);
        }else{
            return count(l, tree[i].m, 2 * i)
                 + count(tree[i].m + 1, r, 2 * i + 1);
        }
    }
}

void setv(){
    int n, v;
    scanf("%d%d", &n, &v);
    insert(n, v);
}

void measure(){
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", count(l, r));
}

int main(){
    int casec = 1, N, first = 1;
    char t;
    while(scanf("%d", &N), N != 0){
        if(first) first = 0;
        else putchar('\n');
        for(int i = 1; i <= N; ++i) scanf("%d", res+i);
        getchar();
        printf("Case %d:\n", casec++);
        make(1, N);
        while(true){
            t = getchar();
            if(t == 'M') measure();
            else if(t == 'S') setv();
            else if(t == 'E') {
                while(t = getchar(), t != '\n' && t != EOF);
                break;
            }
            while(t = getchar(), t != '\n' && t != EOF);
        }
    }
    return 0;
}




Generated by Bo-blog 2.1.0