セグメント木(SegmentTree)

はじめに

何年もやってみようという意志だけがありました。
難しいが汎用性が高く解ける問題の傾向が広がるという印象があります。
体感週に1,2回くらいの頻度で遅延セグ木という文字列をTwitterで観測します(伝家の宝刀!!ってやつ)。

セグ木とは

正式名称はセグメント木(SegmentTree)
以下の操作を高速に行えるデータ構造です。

要素の代入
要素の取得
区間操作

上記の操作を時間計算量O(log N)で行えます。すごい、、

目標

O(log N)を感じることを目標とします。
そしたら仕組みが理解できたと言えるんじゃないか?の気持ちで、

本編

まず、前提としてセグ木は完全二分木です。
操作したい配列を葉に持ちます。
親ノードが2つの子ノードのうち、小さいほうの値を持ちます。

現在の状態をC++で書くとこんな感じ(以降全てC++)。
変数の名前が適当ですがすみません。

#include <iostream>
#include <vector>
using namespace std;
int main(){
   //操作したい元の配列を用意します。
   vector<int> a={1,6,3,7,8,3,5,7};
   //今後使いやすいので宣言しておきます。
   int a_size=a.size();
}

セグ木の初期化

さて、ここからセグ木本体を用意していくことになりますが、大きさと初期化をどう行うか書きます。
先ほどの画像を見るとわかる通り、ノードの数は全部でa.size()×2-1個であることがわかります。
ここで1-indexedにしてみるとセグ木の大きさはa.size()×2になりますね。

そして葉には元の配列aをそのまま入れます。

ここまでを反映させるとこんな感じ。

#include <iostream>
#include <vector>
using namespace std;
int main(){
   //操作したい元の配列を用意します。
   vector<int> a={1,6,3,7,8,3,5,7};
   //今後使いやすいので宣言しておきます。
   int a_size=a.size();

   //セグ木本体を用意 大きさは元の配列aの大きさの二倍です。
   //また、それらを大きな数で初期化します。
   vector<int> segment_tree(a_size*2,0);
   for(int i=a_size;i<a_size*2;i++) segment_tree[i]=a[i-a_size];
}

現状
segment_tree = {0,0,0,0,0,0,0,0,1,6,3,7,8,3,5,7}

segment_treeの完成

次にsegment_treeの準備をします。

各ノードの親子関係について注目してみましょう。
すると、子のindexは親のindexの2倍と2倍+1であることがわかります。
逆に言えば親index = 子index / 2であるといえます。
親は子の小さいほうの値を持つので葉から順に根に向かって操作したいですね。
今回で言うと7indexから見ていきます。

#include <iostream>
#include <vector>
using namespace std;
int main(){
   //操作したい元の配列を用意します。
   vector<int> a={1,6,3,7,8,3,5,7};
   //今後使いやすいので宣言しておきます。
   int a_size=a.size();

   //セグ木本体を用意 大きさは元の配列aの大きさの二倍です。
   //また、それらを大きな数で初期化します。
   vector<int> segment_tree(a_size*2,0);
   for(int i=a_size;i<a_size*2;i++) segment_tree[i]=a[i-a_size];

   //segment_treeを根まで埋める
   for(int i=a_size-1;i>=0;i--) segment_tree[i]=min(segment_tree[i*2],segment_tree[i*2+1]);
}

現状
segment_tree={0,1,1,3,1,3,3,5,1,6,3,7,8,3,5,7}

segment_treeが完成しました！

要素の代入(更新)について

では適当に、8 → 10に更新することにします。
元の配列aを見ると要素が8なのはa[4]ですね。
すなわち元の配列aでいうとindex=4, value=8、segment_treeでいうとindex=12(a-index + a_size), value=8ということです。

先にコードを見た方がイメージしやすい気がするので書きます。

#include <iostream>
#include <vector>
using namespace std;
int main(){
   //操作したい元の配列を用意します。
   vector<int> a={1,6,3,7,8,3,5,7};
   //今後使いやすいので宣言しておきます。
   int a_size=a.size();

   //セグ木本体を用意 大きさは元の配列aの大きさの二倍です。
   //また、それらを大きな数で初期化します。
   vector<int> segment_tree(a_size*2,0);
   for(int i=a_size;i<a_size*2;i++) segment_tree[i]=a[i-a_size];

   //segment_treeを根まで埋める
   for(int i=a_size-1;i>=0;i--) segment_tree[i]=min(segment_tree[i*2],segment_tree[i*2+1]);

   //修正するindexを指定
   int idx = 4+a_size;
   segment_tree[idx] = 10;
   while(idx!=0){
      idx/=2;
      segment_tree[idx]=min(segment_tree[idx*2],segment_tree[idx*2+1]);
   }
}

現状
segment_tree={0,1,1,2,1,3,2,5,1,6,3,7,2,3,5,7}

あれ????なんか`O(log N)`を感じてきたぞ!!!!!!!

だって完全二分木の根の高さはO(log N)ですよね！！
更新する回数は高さ分だけ、つまりO(log N)回なのです！！！うおお！！！

区間操作について(最小値)

さて、これが私が直感に反している部分です。
考え方は理解している状態です。
今までちゃんと落ち着いて考えたことがないのでここで腰を据えます。

現状の理解

右と左から同時に見ていって、いい感じに親に上がっていく。
右<左が成り立つ間ループを回し続ける。
はい、この程度です。
ですが左からの操作は合ってると思います。

左から

まず、現在最小値を求めたい半開区間[l,r)について左端から順にみる。
ここで、今見ているノードのindexが奇数の場合はそのindexに入っている要素を取得する。
偶数の場合は親を見る。

右から

こちらの記事を参考にさせていただきました。

な、、、なるほど。。。。
右からの場合でも変わらず奇数indexならその左側を採用するんですね。
ということは、採用と親ノードへの移動がセットになって同時に行われていることになります。

まとめると、

左からの操作では、奇数indexならば採用してからindexを+1する。
右からの操作では、奇数indexならばindexを-1してからindexに対応する要素を採用する。
そしてどちらも偶数indexならば親ノードへ移動する。

#include <iostream>
#include <vector>
using namespace std;
int main(){
   //操作したい元の配列を用意します。
   vector<int> a={1,6,3,7,8,3,5,7};
   //今後使いやすいので宣言しておきます。
   int a_size=a.size();

   //セグ木本体を用意 大きさは元の配列aの大きさの二倍です。
   //また、それらを大きな数で初期化します。
   vector<int> segment_tree(a_size*2,0);
   for(int i=a_size;i<a_size*2;i++) segment_tree[i]=a[i-a_size];

   //segment_treeを根まで埋める
   for(int i=a_size-1;i>=0;i--) segment_tree[i]=min(segment_tree[i*2],segment_tree[i*2+1]);

   //要素の代入(更新)
   //修正するindexを指定
   int idx = 4+a_size;
   segment_tree[idx] = 10;
   while(idx!=0){
      idx/=2;
      segment_tree[idx]=min(segment_tree[idx*2],segment_tree[idx*2+1]);
   }

   //半開区間の最小値
   //最終的な答え mn_elem を大きな値で初期化
   int mn_elem = 10^9;
   int left = 1 + a_size, right = 7 + a_size; //rightは半開区間なので6indexまでの場合+1して7になる
   while(left<right){
      if(left % 2 != 0){
         mn_elem=min(mn_elem,segment_tree[left]);
         left++;
      }
      if(right % 2 != 0){
         right--;
         mn_elem=min(mn_elem,segment_tree[right]);
      }
      left/=2;
      right/=2;
   }
   //最小値の出力
   cout<<ans<<endl;
}

最後に

かなり理解度が深まりました。
コンテスト本番で気づいて実装してってのはまだできるかわかりませんが(ライブラリにするかも)、今後には必ず生きてくると思います。
練習問題が沢山まとまっているので解いて慣れようと思います。
凄い充実した気分になれました。

おわり