example of coding about range query problem in 14th KMC slide

rmq_segtree.cpp

#include<bits/stdc++.h>
using namespace std;

// Range Minimum Query in Segment Tree.

struct range_minimum_query{
  // 管理したい元の配列のサイズ以上の2冪。
  int n;
  // セグメント木(完全二分木)を管理する一次元配列。
  vector<int> segtree;
  // minの単位元としてのINF。値は2^31-1。
  const int INF = INT_MAX;
  
  // @param sz 管理したい元の配列のサイズ
  // nをsz以上の2冪にし、セグメント木のサイズを2*n-1、値をINFに初期化する。
  range_minimum_query(int sz){
    for(n = 1; n<sz;) n <<= 1;
    segtree.assign(2*n-1,INF);
  }
  
  
  // 元の配列の[l,r)のminを求める。
  // @param l,r [l,r)が求めたいminの元の配列での範囲。
  // @param a,b [a,b)が現在見ている頂点の持つminの元の配列における範囲。
  // @param k   セグメント木の現在見ている頂点のindex
  // @return    セグメント木により、求められた[l,r)の最小値。
  // 上からDFSして、[l,r)内の頂点であれば自身の値を返し、そうでなければ単位元を返す。
  // このようにして帰ってきた値を全てminしたものが求めたいものである。
  // デフォルト引数にn(非staticなメンバ変数)を指定できないため、オーバーロードしている。
  int find(int l, int r){
    return find(l,r,0,n,0);
  }
  int find(int l, int r, int a, int b, int k){
    // [a,b)が[l,r)の外側なら、影響のない単位元INFを返す。
    if(b<=l || r<=a) return INF;
    
    // [a,b)が[l,r)の内側なら、その頂点は[l,r)内で最も大きい区間minを持つので、それを返す。
    else if(l<=a && b<=r) return segtree[k];
    
    // どちらでもなければ(解説スライドでの赤線を跨いでいる状態)、もっと細分されたものを確認する必要があるため、子を確認する。
    // 左側の子は[a,(a+b)/2)の区間minを持ち、indexは2*k+1
    // 右側の子は[(a+b)/2,b)の区間minを持ち、indexは2*k+2
    // この２つの[l,r)内の区間minのminを返してやれば良い。
    // 現在見ている頂点が葉に該当する場合は必ず上の２つの条件のどちらかで捕捉されるため考えなくて良い。
    else return min(find(l,r,a,(a+b)/2,2*k+1), find(l,r,(a+b)/2,b,2*k+2));
  }
  
  // 指定した頂点とその影響する範囲の値を更新する。  
  // @param i 書き換えたい値の元の配列におけるindex
  // @param x 更新後の値
  void update(int i, int x){
    // 解説スライドの通り、元の配列を持つ最下段の長さをn(2冪)とすると、
    // その上のセグメント木の構造を持つ部分は n/2 + n/4 + n/8 + .. + 1 = n-1(等比級数の公式より)
    // よって、元の配列を最初に更新したいので、元の配列部分のindexに修正するため、n-1を加える。
    i += n-1;
    
    // その頂点をxに更新する。
    segtree[i] = x;
    // 更新した最下段の情報の影響する範囲を更新する。
    // 具体的には更新した頂点の祖先全てが対象となる。
    while(i>0){
      // 親ノードへと移動
      i = (i-1)/2;
      // 自分の子２つを比較し、小さい方を得る。
      segtree[i] = min(segtree[2*i+1], segtree[2*i+2]);
    }
  }
};

// 使用例
int main(){
  range_minimum_query rmq(10);
  rmq.update(5,3); // 5番目の頂点を3に更新する。
  cout << rmq.find(0,3) << endl; // [0,3)の区間minを出力。区間内の全頂点が未更新なので、出力値はINF=2^31-1
  cout << rmq.find(3,7) << endl; // [3,7)の区間minを出力。5番目の頂点のみが更新されているので、出力値は3
}

rmq_sqrt_decomposition.cpp

#include<bits/stdc++.h>
using namespace std;

// Range Minimum Query in sqrt decomposition.

// 各バケットの区間幅。だいたい√max(N)くらいになるように設定しよう。
const int width = 512;

struct sqrt_decomposition{
  // minの単位元 2^31-1 の値を持つ。
  const int INF = INT_MAX;
  
  // n:元の配列のサイズ。
  // k:バケットの総数。
  int n, k;
  
  // data:元の配列
  // bucket:バケット。widthごとの最小値を持つ。
  vector<int> data, bucket;

  // @param sz 初期化したい、元の配列のサイズ。
  // 各メンバ変数を初期化する。
  sqrt_decomposition(int sz){
    n = sz;
    // n/widthの切り上げ。バケットはこれだけあれば十分
    k = (n+width-1) / width;
    // 配列外参照しないように、配列自体はバケットが覆う区間全てを持っておく。
    data.assign(k*width, INF);
    // バケットを初期化。
    bucket.assign(k,INF);
  }
  
  // 区間[l,r)のminを調べる。
  int find(int l, int r){
    int res = INF; //返り値。単位元INFで初期化しておく。
    
    // バケットを全て探索し、バケットの管理する区間[a,b)が
    // [l,r)の外側ならスキップ。
    // [l,r)の内側ならバケットの値とresを比較し小さい方を代入。
    // [l,r)の境界上にあるなら、[a,b)との共通区間である[max(l,a),min(r,b))を全て調べる。
    for(int i=0; i<k; ++i){
      // 各バケットが管理する区間[a,b)
      int a = i*width, b = (i+1)*width;
      // 外側：スキップ
      if(b <= l || r <= a) continue;
      // 内側：バケットの値とresを比較
      else if(l <= a && b <= r) res = min(res, bucket[i]);
      // 境界：[l,r)と[a,b)の共通部分を全て調べ、resと比較。
      else{
        for(int j = max(a,l); j < min(b,r); ++j){
          res = min(res, data[j]);
        }
      }
    }
    return res;
  }

  // i番目の要素をxに更新し、影響するバケットも確認して更新する。
  void update(int i, int x){
    // 大元のデータを更新。
    data[i] = x;
    // 該当するバケットのindex
    int bid = i/width;
    // そのバケットの管理する区間[a,b)
    int a = bid*width, b = (bid+1)*width;
    // 最終的にバケットに代入される値。[a,b)の最小値。
    int minval = x;
    // [a,b)内の全ての要素を確認し、minvalと比較、更新する。
    for(int j = a; j < b; ++j){
      minval = min(minval, data[j]);
    }
    // バケットをその値で更新する。
    bucket[bid] = minval;
  }
};

int main(){
  sqrt_decomposition rmq(10); // サイズ10の配列を考え、平方分割する。
  rmq.update(5,3); // 5番目の頂点を3に更新する。
  cout << rmq.find(0,3) << endl; // [0,3)の区間minを出力。区間内の全頂点が未更新なので、出力値はINF=2^31-1
  cout << rmq.find(3,7) << endl; // [3,7)の区間minを出力。5番目の頂点のみが更新されているので、出力値は3
}

rsq_binary_indexed_tree.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct fenwick_tree{
  //0-indexed
  //1-indexed用のコードを0-indexedに落とし込む処理をしているため、可読性がちょっと低い

  // nは元の配列且つBITのサイズ。
  // BITでは、元の配列と同じサイズの配列で管理できる。
  ll n;
  
  // bitを格納する配列
  vector<ll> bit;
  fenwick_tree(int sz){
    n = sz;
    
    // bitをサイズn, 値を0で初期化。
    bit.assign(sz,0);
  }
  //add a-th factor w;
  void add(ll a,ll w){
    //0-indexedで入ってきたaをa+1にして、1-indexedに
    //そして各値にアクセスするときだけindexを1減らす
    for(ll i=a+1;i<=n;i+=i&-i) bit[i-1] += w;
  }
  //return sum [0,a)
  ll sum(ll a){
    ll res = 0;
    //0-indexedで入ってきたaをa+1にするが、半開区間なのでa+1-1=aになる
    for(ll i=a;i>0;i-=i&-i) res += bit[i-1];
    return res;
  }
  //return sum [a,b)
  ll sum(ll a,ll b){
    return sum(b)-sum(a);
  }
};

int main(){
  // rsqの単位元は0なので、値を全て0にして初期化する。
  fenwick_tree rsq(10);
  rsq.add(5,2); // 5番目の値に2を加える。
  rsq.add(3,1); // 3番目の値に1を加える。
  cout << rsq.sum(6) << endl; // [0,6)の区間和を出力。結果として3を出力する。
  cout << rsq.sum(3,5) << endl; // [3,5)の区間和を出力。結果として1を出力する。
}

All files are verified in AOJ.