## 2013年11月25日月曜日

### BIT(Fenwick Tree)でRMQ

値の更新ありのRMQは普通セグメント木で解くが、実はBITでも解ける。こんな感じ。query関数内の[l, r]がセグメントに含まれていないときの処理の仕方がかっこいい。
計算量は、queryはO(logN)、updateはO(log2N)。
```#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;
}
```