2020/3/1に行われたABC157は、 E問題でSegment Treeを使って解ける問題が出題されました。
(これ以外の解法でも解けますが、思考に必要なリソースを減らして解けるので便利。)
以前からSegment Tree(=セグ木)という単語はよく目にしていたのですが、
よく分かっていなかったので、これを期に勉強してみます。
色々偉そうに書いてますが、筆者は記事を書いている時点で緑コーダーですし、
誤りを含んでいる可能性がありますので、ご了承ください。
Segment Treeそのものの解説記事はもう世の中に無数にありますが、
秋葉さん(iwiwi)のスライド
セグメント木について - beet's soil
セグメント木をソラで書きたいあなたに - hogecoder
上記のbeetさんの記事から引用すると、
「セグ木とは、前計算と最小限の更新で、区間に対する操作を受け止めることができるデータ構造のこと」
であり、私もそういう理解をしています。
segment treeは
(とある条件を満たした)N要素の配列に対して、ある条件を満たすような処理をいくつもしなければならないときに必要となるデータ構造で、
具体的には完全2分木を使い、木の葉(?) と言っていいのか分かりませんが、とにかく末端の部分に計算対象の配列を埋め込み、
それ以外の木の頂点に、とある計算結果を保存しながら再利用していくことで実現します。
セグ木にはどうやらいくつも種類があるようですが、
この記事では、今回の問題(ABC157-E)で必要となった、「一点更新区間取得」型のセグ木について整理します。
下記、断りなしにセグ木、segment treeなどと書きますが、「一点更新区間取得」型のセグ木のことを表すことにします。
「
一点更新区間取得型」のセグ木では、配列に対して以下の2種類の処理を高速で扱うことができます。
- 配列のうち1つの要素を選んで、別の値に書き換える(一点更新)
- 配列のうち、とある連続した範囲を選んで、その範囲に含まれる全ての要素について(とある条件を満たした)二項演算をした結果を求める(区間取得)
のことです。
良い表現が思いつかないので、「全ての要素について二項演算」という分かりにくい表現になってしまいましたが、
念のために補足します。
二項演算というのは、二つの値から一つの値を求める演算のことで、
(専門じゃないので自信は無いですが、数学的な表現だと、
集合Sの任意の2要素a,b∈Sに対して定義される演算a×bの結果が再びSの要素になれば、その演算は二項演算であると言えるのだと理解しています)
例えば加減乗除は二項演算です。
他にも、2つの要素の最大値を求める演算(max関数)、2つの正整数の最大公約数を求める演算(C++でいう__gcd)なども二項演算であるといえます。
ただ、どんな要素が入った配列でも、どんな二項演算でもSegment Treeが適用できるのかというとそうではなくて、
下記のような条件があります。(とある条件を満たした、と書いたのはそのせいです)
- 配列の要素が含まれる集合には、演算に対する単位元が存在すること
- 演算は結合法則を満たすこと
1つ目の条件をもう少しかみ砕くと、「どんな要素xを持ってきても、とあるiと二項演算をすると答えがxになってしまうようなiが存在すること」となります。
例えば、0以上の整数に対して足し算という二項演算を考えた時、
どんな0以上の整数Mを持ってきても、0を足すと答えはMとなる(M+0=M)ので、
「0は"0以上の整数"の"足し算"における単位元である」と言えます。
もう一つの例として-(231-1)から231-1の間にある(すなわちint型で表現できる)整数に対して、最大値を求めるという二項演算を考えた時、
どんな(上記の範囲に含まれている)整数Mを持ってきても、-(231-1)との最大値を求めると答えはMとなりますので、
「-(231-1)は、"int整数型に含まれる整数"のうち、2つの整数の"最大値を求める演算"における単位元である」といえます。
もちろん、どんな集合・どんな演算を持ってきても単位元が存在するわけではなくて、
例えば、正整数(1以上の整数)における足し算は単位元が存在しません。
さて、2つ目の条件はシンプルで、演算の順番を変えても結果が変わらないことです。
そもそもこの条件が無いと、「全ての要素について二項演算」をしたときに一意に結果が定まりません。
全ての要素について二項演算、というのは、
例えばa,b,c,dという要素があって、これら全ての要素について"・"という二項演算する場合は、
(((a・b)・c)・d)と演算をすることを指しています。
例えば足し算なら(((a+b)+c)+d)ですし、掛け算なら(((a*b)*c)*d)です。
これらは順番を変えても最終的な結果は変わりません。
最大値を求める演算なら
max(max(max(a,b),c),d)
です。ここでa,b,c,dをどう入れ替えても最終的な結果は変わりません。
逆に引き算や割り算は演算の順番を変えると結果が変わります。
(5-2)-3=0だが、5-(2-3)=6
などの例を見れば明らかです。
長くなってしまいましたが、とにかくN要素の配列に関して、
- 配列のうち1つの要素を選んで、別の値に書き換える(一点更新)
- 配列のうち、とある連続した範囲を選んで、その範囲に含まれる全ての要素について(とある条件を満たした)二項演算をした結果を求める(区間取得)
これらの処理を高速で行います。
実際にどういうアイデアでこれらを処理していくかについては、
既に秋葉さん(iwiwi)のスライドで(p.44から)で説明されているので、ここでは割愛します。 (ここが一番重要かつ本質の部分ですが、既に優れた説明があるので、引用してサボります) 補足すると、このスライドでは8個の要素の配列に関して、(一点更新)ある要素の値を書き換える処理、(区間取得)とある連続した区間を選んで、その範囲に含まれる要素の最小値を求める処理を高速に扱うことを考えています。 この問題はRMQ(range minimum query)として広く知られているらしく、セグ木の典型問題となっています。 上記のスライドでどういう処理をしなくてはならないか理解した上で、丁寧なライブラリを書いていきます。 AOJ(Aizu Online Judge)にちょうどRMQそのまんまの問題があるので、 これを解くことを意識したコードを書いてみます。
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
struct SegmentTree {
private:
int n;
vector<int> node;
//int nとvector<int> nodeの2つを変数に持つ。
//nは扱う配列の要素数で、nodeはまさにsegtree本体
public:
//初期化処理。segtreeを使うときは最初にこれを宣言する。
SegmentTree(vector<int> v) {
int sz = v.size(); //vは扱う配列の長さ
n = 1; while(n < sz) n *= 2; //nはvの配列を全て入れるために必要なseg treeの葉の数
node.resize(2*n-1, INF); //★演算によって単位元を変える。segtreeでは全部で2n-1の配列が必要。
//最小値を求めるのであれば、最初は単位元であるINFで初期化しておく
//例えばv.size()が2のべき乗で無かった場合は、最終的な計算結果に影響のないような単位元の葉を用意しておく必要がある
for(int i=0; i<sz; i++) node[i+n-1] = v.at(i); //segtreeの葉の部分に扱う配列を埋め込む
for(int i=n-2; i>=0; i--) node[i] = min(node[2*i+1],node[2*i+2]);
//★演算によって変える場所 segtreeを作る(注目しているnode iの子ノードを見て二項演算をして、node iの値を決定する)
}
void update(int x, int val) {
//一点更新処理。x番目の要素をvalに変更する
x += (n - 1); //配列のx番目の要素を更新しようとするとき、segtreeで対応する要素はx+n-1番目である
node[x] = val; //segtree上で値を更新
while(x > 0) { //葉から根に向かってsegtreeの要素を更新していく
x = (x - 1) / 2;
node[x] = min(node[2*x+1],node[2*x+2]); //★演算によって変える
}
}
int getor(int a, int b, int k=0, int l=0, int r=-1) {
//区間取得処理。求めたいのは区間[a,b)の中で演算しつづけた結果(たとえばこの区間の最小値)
//ノードkは元の配列でいうとどの区間をカバーしているか？を表すindex
if(r < 0) r = n; //最初に呼び出す時はノードk=0はsegtreeの根なので区間は[0,n)を指す
if(r <= a || b <= l) return INF;
//★演算によって変える 今のノードが求める区間と無関係の場合は、
//最終的な答えに影響しない単位元(最小値を求めたい場合は単位元はINF)を返す
if(a <= l && r <= b) return node[k];
//今見ている区間[l,r)が答えを求めたい区間[a,b)に完全に含まれるなら
//この区間について演算し続けた結果(=node[k];例えば最小値)を返す
//上記に当てはまらない場合
//kの子ノードを見に行って、再帰的に処理を行う k=0の場合はノード1と2を見る
int vl = getor(a, b, 2*k+1, l, (l+r)/2);
//kの子ノード(left)の子孫のうち、求めたい区間に含まれる要素について演算し続けた結果を返す
int vr = getor(a, b, 2*k+2, (l+r)/2, r);
//kの子ノード(right)の子孫のうち、求めたい区間に含まれる要素について演算し続けた結果を返す
return min(vl,vr); //★演算によって変える場所 子ノードの子孫のうち、演算しつづけた結果を返す
}
};
int main(){
int N; cin >> N;
vector<int> a(N,INF);
SegmentTree tree(a);
int Q; cin >> Q;
for(int i=0;i<Q;i++){
bool type; cin >> type;
if(!type){
int first,second; cin >> first >> second;
tree.update(first,second);
}else{
int first,second;
cin >> first >> second;
cout << tree.getor(first,second+1) << endl;
}
}
}
まずはstruct(もしくはclass?)を用いてsegment treeを定義します。 struct,classはAtCoderの学習用コンテンツ APG4bの説明が分かりやすいです。 AB - 3.04.構造体 https://atcoder.jp/contests/apg4b/tasks/APG4b_ab?lang=ja structの中に、初期化処理と2種類の処理
(一点更新)と
(区間取得)を実装していきます。
〇
初期化処理 Segment Treeの中だけで使えるprivate変数int nとvector<int> nodeを用意します。
nはクエリを処理したい対象の配列のサイズで、nodeはsegment treeそのものを実装するための配列です。
上記秋葉さんのスライドにもある通り、n要素について、segment treeを実装するためには
2n-1個の配列要素が必要になります。
(正確に言えば、2のべき乗の中でnより大きく且つ最小のものをmとすれば
2m-1個の配列要素が必要になります)
segment treeの葉(根から一番離れている頂点)にn個の配列を埋め込み、他の頂点に関して二項演算した結果を入れていきます。
〇
一点更新 2つの引数は、「どこの要素を」「何の値に」更新するかを表します。
まずは、nodeの葉の中で更新したい要素に対応する部分を更新します。
その後、その葉の親のノードに注目し、2つの子ノードの値を二項演算した結果を計算し(今回の場合は2つの子ノードの最小値を計算する、という意味です)、更新する必要があれば自分自身のノードの値を更新します。
またその親ノードに注目し… ということを繰り返して根まで更新し続けたら処理は終了です。
この処理にかかる計算時間は
O(logN)です。
〇
区間取得 引数は演算結果を求めたい範囲[a,b)です。
範囲は半開区間で考えていることに注意してください。
[0,100)なら
0<=i<100、すなわち0から99までです。
例えばn=16のときに[1,6)の最小値を求めることを考えながら理解していきましょう。
最初[0,n)の区間に求めたい範囲は含まれるか？を考えます。
求めたい区間が含まれていますので、ここで区間を分割して、[0,8)と[8,16)とします。
[0,8)と[1,6)の共通部分の最小値を求めた結果をA,
[8,16)と[1,6)の共通部分の最小値を求めた結果をBとして、
min(A,B)を計算すれば求めたい最小値が出てくるでしょう。
しかし、[8,16)と[1,6)には共通部分はありませんので、ここで計算しても無意味です。
[0,8)と[1,6)の共通部分の最小値がそのまま最終的な答えになってほしいので、Bとして単位元のINFを出力しておきます。
(
min(A,B)=min(A,INF)=Aと計算できる)
結局、[0,8)と[1,6)の共通部分の最小値を計算すれば最終的な答えが出てくることになりました。
さらに[0,8)の区間を分割して[0,4)と[4,8)とし、同様に考えていきます。
このような操作を繰り返していくことで、最終的に最小値を求めることができます。
こちらも処理にかかる計算時間は
O(logN)です。
main関数の中身の説明は割愛します。
このようにして、1クエリあたり
O(log N)で処理出来るデータ構造がsegment treeです。
ナイーブに実装すると、一点更新は定数時間で処理できるが、区間取得は最悪1回あたり
O(N)かかることになるので、
一点更新と区間取得が大量かつバラバラに何回くるか分からない場合はsegment treeが有効と言えると思います。
上のAOJの問題の例だと、
N=106かつ
Q=106なので、
ナイーブに実装する場合最悪
O(N*Q)=O(1012)ですが、segment treeを使うと
O(QlogN)=O(107)程度で抑えられますね。
