UVA 12086 Potentiometers ( 平方分割 Range Sum Query )

UVa Online Judge
Range Sum Query の基礎問題を平方分割で処理した。
ncastar.hatenablog.com
この記事が大変参考になりました。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;

int kase;
int n;
int a[ MAXN ];

int BS;
vector< int > bucket;

void init(){
    bucket.clear();
    BS = sqrt( n ) + 1;
    int sum = 0, cnt = 0;
    for(int i = 0; i < n; ++i){
        sum += a[ i ];
        ++cnt;
        if( cnt == BS ){
            cnt = 0;
            bucket.push_back( sum );
            sum = 0;
        }
    }
    if( cnt ) bucket.push_back( sum );
}

void update(int k, int x){
    int bk = k / BS;
    bucket[ bk ] -= a[ k ];
    bucket[ bk ] += x;
    a[ k ] = x;
}

int qsum(int ql, int qr){
    int bl = ql / BS;
    int br = qr / BS;
    int res = 0;
    if( bl == br ){ // needs extra care
        for(int i = ql; i <= qr; ++i)
            res += a[ i ];
    } else{
        int lt = ( bl + 1 ) * BS;
        for(int i = ql; i < lt; ++i)
            res += a[ i ];
        int rs = br * BS;
        for(int i = rs; i <= qr; ++i)
            res += a[ i ];
        for(int i = bl + 1; i < br; ++i)
            res += bucket[ i ];
        
    }
    return res;
}

int main(){
    while( scanf("%d", &n) == 1 && n ){
        for(int i = 0; i < n; ++i)
            scanf("%d", a + i);
        if( kase ) puts("");
        printf("Case %d:\n", ++kase);
        init();
        while( true ){
            char op[ 10 ]; scanf("%s", op);
            if( op[ 0 ] == 'E' ) break;
            int x, y; scanf("%d%d", &x, &y);
            if( op[ 0 ] == 'S' ) update( --x, y );
            else printf("%d\n", qsum( --x, --y ));
        }
    }
    return 0;
}