gistfile1.txt

Starry Sky木についてと、qnighyによるStarry Sky木の実装


** Starry Sky木とは

整数区間[0,n)に対して、1つずつ実数値が割りあてられている。
これに対して、以下の2つのクエリにO(log n)時間で応答するデータ構造を
Starry Sky木と呼ぶ。

(1) 整数区間S⊂[0,n)と重みWが与えられたとき、S内の全ての要素にWを加算する。
(2) 整数区間S⊂[0,n)が与えられたとき、S内の要素のうち最大のものを返す。

ただし、以下に注意すること。
(a) この呼称は日本情報オリンピック参加者の一部による呼称であり、日本情報オリンピック2009年の春合宿の問題「Starry Sky」で必要なデータ構造であったことに由来する。
(b) Starry Sky木はいくつかの実装方法があり、それらの総称にすぎない。

** Starry Sky木のqnighyによる実装

まず、木は完全二分木の配列表現を用いる。

1つの節点はある区間に対応し、その2つの子は親の区間を二分する。
末端の節点は1つの要素に対応する。

各節点は1つの数値をもつ。
ある要素の値は、その要素に対応する節点およびその祖先全ての和である。

また、最大値を容易に検索できるようにするため、以下の制約を設ける。
すなわち、兄弟である2つの節点(a,b)について、aとbの片方は0であり、もう片方は0以下である。

例えば以下のようになる。

(             15              )
(    -1       ) (      0      )
( -4  ) (  0  ) (  0  ) ( -3  )
  0 -10 -11   0   0 -10   0  -3
-------------------------------
 10   0   3  14  15   5  12   9

例えば、先頭の要素は、0+(-4)+(-1)+(15)=10として求めることができる。

このとき、最上位の節点は常に最大値を指し示す。(この場合15)。

詳細は考えてもらえばわかるが、ある区間の更新は、下から上に登るように走査することで、O(log n)時間で行うことができる。

また同様に、任意の区間の最大値をO(log n)で求めることができる。