BIT(Fenwick Tree)でRMQ

　値の更新ありのRMQは普通セグメント木で解くが、実はBITでも解ける。こんな感じ。query関数内の[l, r]がセグメントに含まれていないときの処理の仕方がかっこいい。
　計算量は、queryはO(logN)、updateはO(log²N)。

#include <iostream>
#include <cstdlib>
#include <cassert>

using namespace std;

const int N = 100000;    // # of elements in array
const int Q = 100000;    // # of queries
int a[N+1];
int bit[N+1];

int query( int l, int r ) {
    int m = 0;

    while (l <= r) {
        int p = r - (r & -r);       // p+1 is the left end of this segment
        if (p+1 >= l) {             // when [l, r] is completely included in this segment
            if(a[bit[r]] > a[m])
                m = bit[r];
            r -= r & -r;            // move to the next segment
        } else {                    // when [l, r] is not completely included in this segment
            if (a[r] > a[m])
                m = r;
            --r;                    // shrink the segment
        }
    }

    return m;
}

void update(int x) {
    for(int y = x; y <= N; y += y & -y) {
        if(bit[y] == x) {           // the maximum value was at the x-th position, but its value has changed
            int z = query(y-(y&-y)+1, y-1);
            if (a[y] > a[z])
                bit[y] = y;
            else
                bit[y] = z;
        } else {
            if(a[bit[y]] < a[x])
                bit[y] = x;
        }
    }
}

int main(int argc, char **argv) {
    srand(time(NULL));
    
    for (int i = 1; i <= N; i++) {
        a[i] = rand();
        update(i);
    }

    for (int i = 0; i < Q; i++) {
        int type = rand() % 2;

        if (type) {
            int x = rand() % N + 1;
            int v = rand();
            a[x] = v;
            update(x);
        } else {
            int l = rand() % N + 1;
            int r = rand() % N + 1;
            int x = query(l, r);
            
            for (int j = l; j <= r; j++)
                assert(a[x] >= a[j]);
        }
    }

    cout << "success" << endl;
    
    return 0;
}