RMQ using BIT

An implementation of this document: https://ioinformatics.org/journal/v9_2015_39_44.pdf

Update O(log n), query O(log n). Update is slightly slower than segtree based RMQ, but query is slightly faster. I have written it once before, but it is not available now. So I write down here.

const int N = 1 << 17;
int L[N + 1], R[N + 1];

void update(int k, int v) {
  k++;
  int l = k;
  int r = k + 1;
  if (~k & 1) {
    L[r] = v;
  } else {
    R[l] = v;
  }
  for (int i = 1; i < N; i <<= 1) {
    if (~k & 1) {
      r += i;
    } else {
      l -= i;
    }
    k >>= 1;
    int m = l + r >> 1;
    if (~k & 1) {
      L[r] = min(L[m], R[m]);
    } else {
      R[l] = min(L[m], R[m]);
    }
  }
}

int query(int l, int r) {
  l++;
  r++;
  int res = 1e9;
  for (int i = r; i - (i & -i) >= l; i -= i & -i) {
    res = min(res, L[i]);
  }
  for (int i = l; i + (i & -i) <= r; i += i & -i) {
    res = min(res, R[i]);
  }
  return res;
}

Benchmarks are here.
BIT: https://ideone.com/pxkwH8
SEG: https://ideone.com/Lo1vJQ

In my environment, the results are as follows:

random: 0.0781
update: 0.9844
update-random: 0.9062
query: 0.4688
query-random: 0.3906
result: 864747476
random: 0.0625
update: 0.3594
update-random: 0.2969
query: 1.1250
query-random: 1.0625
result: 864747476