莫隊演算法
===
###### tags: `Algorithm`

* 使用條件
* 允許離線
* 區間查詢 + 修改
* 可以在很短的時間知道邊界相鄰位置的答案
* [l - 1, r], [l + 1, r],[l, r + 1],[l, r - 1]
* 特點
* 複雜度 `O( n * n^(1\2))`
* 核心
* **分組排序法**: 先按左界排序後, 分組, 在組內按右界排序
* 實現
* (l\s, r) 字典序排序
## 實現

### 核心語句

* 排序

inline bool  operator < ( const Q &b){
    return (blk == b.blk)?  (r < b.r) : (blk < b.blk);
}

* 調整列隊

sort( qs, qs+m);

curL = 0, curR = 0, curAns;
rep( i, 0, m){        
    Q &q = qs[i];

    while( q.r > curR) add( curR++);
    while( q.r < curR) sub ( --curR);
    while( q.l > curL) sub( curL++);
    while( q.l < curL) add( --curL);
    anss[ q.i] = curAns;
}

### toj120 區間和

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for( int i =(a); i<(b); i++)
#define DE cout << " ::"
#define maxQ 200010
#define maxN 200010
#define int long long

struct Q{ // Query
    int l, r, i;
    int blk; //block
    inline bool  operator < ( const Q &b){
        return (blk == b.blk)?  (r < b.r) : (blk < b.blk);
    }
}qs[ maxQ]; // queries
int anss[maxQ];
int lim;
int arr[maxN];

int curL, curR, curAns;
inline void add( int i){
    curAns += arr[i];
}
inline void sub( int i){
    curAns -= arr[i];
}


signed main(){
    //freopen( "in.txt", "r", stdin);
    int n; cin >> n;
    rep( i, 0, n){
        cin >> arr[i];
    }
    lim = (int)sqrt(n) + 1;
     
    int m; cin >> m;
    rep( i, 0, m){
        int a, b; cin >> a >> b;
        if( a>b) swap(a, b);
        
        qs[i].l = a-1, qs[i].r = b;
        qs[i].i = i;
        qs[i].blk = qs[i].l / lim;
    }
    
    sort( qs, qs+m);
    
    curL = 0, curR = 0, curAns;
    rep( i, 0, m){        
        Q &q = qs[i];

        while( q.r > curR) add( curR++);
        while( q.r < curR) sub ( --curR);
        while( q.l > curL) sub( curL++);
        while( q.l < curL) add( --curL);
        anss[ q.i] = curAns;
    }
    rep( i, 0, m){
        cout << anss[i] << '\n';
    }
    return 0;
}