セグメント木の抽象化（遅延評価でない）

セグメント木を抽象化したライブラリ(C++)を作成したのでまとめておく。

前提

• セグメント木の実態は完全二分木
• 要素数nを扱いたいならn以上の2冪を葉の数とし、その数をwとすると、全体の要素数は2*w-1個となる
• 完全二分木において、要素i(>0)の親は(i-1)/2、子は(i+1)*2-1, (i+1)*2で参照できる
• セグメント木に必要な機能は基本的にはupdateとqueryの2つだけ
  • update(i, v): i番目の要素をvに更新
  • query(l, r): 区間[l, r)の区間クエリを実行
• セグメント木ではモノイドを管理できる。モノイドとは以下の2つの性質を同時に満たすもの。
  1. 結合則が成り立つ。(A・B)・C = A・(B・C)
     • 最後に載せた問題（AtCoder Regular Contest 008 D タコヤキオイシクナール）が良い例
  2. 単位元eが存在する。単位元とは任意の元Aについて、e・A = A・e = A を満たすもの。（例：乗算における1）

セグメント木のわかりやすい解説記事

www.creativ.xyz

検証用問題

onlinejudge.u-aizu.ac.jp

抽象化前

以下は、RMQに対応するセグメント木である。

/// RMQ用セグメント木
class SegTree{
  private:
  long long e; // 単位元
  long long w; // 葉の数
  vector<long long> tree;
  
  public:
  SegTree(const int n, const long long _e){
    e=_e;
    w=1;
    while(w<n) w<<=1;
    tree=vector<long long>(w*2-1, e);
  }
  
  void update(int i, const long long v){
    i=w-1+i;
    tree[i]=v;
    if(i) while(true){
      i=(i-1)/2;
      int l=(i+1)*2-1, r=(i+1)*2;
      tree[i]=min(tree[l], tree[r]);
      if(i==0) break;
    }
  }
  
  long long query(const int L, const int R, int l=-1, int r=-1, int v=0){
    if(l==-1) l=0;
    if(r==-1) r=w;
    
    if(L<=l and r<=R) return tree[v];
    else if(r<=L or R<=l) return e;
    else{
      long long x=query(L, R, l, (l+r)/2, (v+1)*2-1);
      long long y=query(L, R, (l+r)/2, r, (v+1)*2);
      return min(x,y);
    } 
  }
};

抽象化後

RMQ用セグメント木を汎用化するために、抽象化すべきものは以下の2点。

• セグメント木で持つ物の型
• 更新、区間クエリの処理で使うoperator

よって抽象化後は、セグメント木の呼び出し時に、operatorを新たに付け加える必要がある。

template<class T>
class SegTree{
  private:
  T e;   // 単位元
  int w; // 葉の数
  function<T(T, T)> op; // 区間クエリで使うオペレーター
  vector<T> tree;
  
  public:
  SegTree(const int n, const T _e, const function<T(T, T)> _op){
    e=_e;
    w=1;
    while(w<n) w<<=1;
    tree=vector<T>(w*2-1, e);
    op=_op;
  }
  
  void update(int i, const T v){
    i=w-1+i;
    tree[i]=v;
    if(i) while(true){
      i=(i-1)/2;
      int l=(i+1)*2-1, r=(i+1)*2;
      tree[i]=op(tree[l], tree[r]);
      if(i==0) break;
    }
  }
  
  T query(const int L, const int R, int l=-1, int r=-1, int v=0){
    if(l==-1) l=0;
    if(r==-1) r=w;
    
    if(L<=l and r<=R) return tree[v];
    else if(r<=L or R<=l) return e;
    else{
      T x=query(L, R, l, (l+r)/2, (v+1)*2-1);
      T y=query(L, R, (l+r)/2, r, (v+1)*2);
      return op(x,y);
    } 
  }
};

// 呼び出し側: https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_A
signed main(){
  int n, q; cin>>n>>q;
  auto op=[&](int a, int b){
    return min(a, b);
  };
  auto st=SegTree<long long>(n, (1LL<<31)-1, op);
  
  while(q--){
    int c, x, y; cin>>c>>x>>y;
    if(c==0){
      st.update(x, y);
    }else{
      cout<<st.query(x, y+1)<<endl;
    }
  }
}

抽象化後のライブラリの検証用問題

atcoder.jp