ei1333's page

ホーム > Wiki

セグメント木(Segment-Tree)

説明

完全2分木である。区間に対する様々な演算が$O(\log N)$で実現できるが, ここでは一般的な操作であるRMQを実装している。

実装では木を配列で実現している。ノード $k$ について, 親ノードは $(k - 1) / 2$, 子ノードは $2k+1, 2k+2$ である。

使い方

計算量

実装例

struct SegmentTree
{
  vector< int > seg;
  int sz;
 
  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, INF);
  }

  void set(int k, int x)
  {
    seg[k + sz - 1] = x;
  }

  void build()
  {
    for(int k = sz - 2; k >= 0; k--) {
      seg[k] = min(seg[2 * k + 1], seg[2 * k + 2]);
    }  
  }

  int rmq(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return(INF);
    if(a <= l && r <= b) return(seg[k]);
    return(min(rmq(a, b, 2 * k + 1, l, (l + r) >> 1),
               rmq(a, b, 2 * k + 2, (l + r) >> 1, r)));
  }

  int rmq(int a, int b)
  {
    return(rmq(a, b, 0, 0, sz));
  }

  void update(int k, int x)
  {
    k += sz - 1;
    seg[k] = x;
    while(k > 0) {
      k = (k - 1) >> 1;
      seg[k] = min(seg[2 * k + 1], seg[2 * k + 2]);
    }
  }

};

応用 1: 区間加算

Starry-Sky-Tree と呼ばれる有名なセグメント木がある。このセグメント木では以下の $2$ つのクエリをサポートする。

ここではその区間に一様に加算される値を持つ add 配列と, 区間の最小値を持つ small 配列を持つことによって実現している。

struct SegmentTree
{
  const int INF = 1 << 30;

  vector< int > small, add;
  int sz;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    small.assign(2 * sz - 1, 0);
    add.assign(2 * sz - 1, 0);
  }

  inline void Merge(int k)
  {
    small[k] = min(small[2 * k + 1] + add[2 * k + 1], small[2 * k + 2] + add[2 * k + 2]);
  }

  int rmq(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (INF);
    if(a <= l && r <= b) return (small[k] + add[k]);
    int L = rmq(a, b, 2 * k + 1, l, (l + r) >> 1);
    int R = rmq(a, b, 2 * k + 2, (l + r) >> 1, r);
    return (min(L, R) + add[k]);
  }

  void rangeadd(int a, int b, int x, int k, int l, int r)
  {
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      add[k] += x;
      return;
    }
    rangeadd(a, b, x, 2 * k + 1, l, (l + r) >> 1);
    rangeadd(a, b, x, 2 * k + 2, (l + r) >> 1, r);
    Merge(k);
  }

  int rmq(int a, int b)
  {
    return (rmq(a, b, 0, 0, sz));
  }

  void rangeadd(int a, int b, int x)
  {
    return (rangeadd(a, b, x, 0, 0, sz));
  }
};

応用 2: 遅延評価

遅延評価というテクがある。遅延評価を使うと, 区間に対する演算操作の幅が大きく広がる。

応用 3: 2Dセグメント木

セグメント木のノードに平衡二分探索木をのせた 2Dセグメント木も可能(但し定数倍がかなり重い)。 以下の実装では長方形内の点の個数を求めるクエリと, 点の追加削除のクエリをサポートしている。

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;	
struct SegmentTree
{
  int sz;
  vector< tree< int, null_type, less< int >, rb_tree_tag, tree_order_statistics_node_update > > seg;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.resize(2 * sz - 1);
  }

  int query(int a, int b, int lower, int upper, int k, int l, int r)
  {
    if(a >= r || b <= l) {
      return (0);
    } else if(a <= l && r <= b) {
      return (seg[k].order_of_key(upper) - seg[k].order_of_key(lower));
    } else {
      return (query(a, b, lower, upper, 2 * k + 1, l, (l + r) >> 1) + query(a, b, lower, upper, 2 * k + 2, (l + r) >> 1, r));
    }
  }

  int query(int a, int b, int l, int r)
  {
    return (query(a, b, l, r, 0, 0, sz));
  }

  void update(int k, int x, bool type)
  {
    k += sz - 1;
    if(type) seg[k].insert(x);
    else seg[k].erase(x);
    while(k > 0) {
      k = (k - 1) >> 1;
      if(type) seg[k].insert(x);
      else seg[k].erase(x);
    }
  }
};

問題例

参考資料