週刊 spaghetti_source

値の差分表現

15:06

昨日のは，まるっきり既出でした（iwiさんに教えてもらいました．ありがとうございます）： http://poj.org/problem?id=3580

一般的なので，同じ構造を使う問題があるとは思っていましたが，まさかそのままデータ構造を問う形での出題があるとは思っていませんでした．解説もあるよ：http://poj.org/showcontest?contest_id=1290

しかも，この問題に対する主流の解法が，自分の予定していた解法よりも実装容易だったので，来週まで待たずに解説を張ってしまいます．これから解答を作る予定だった方は，すみません．来週はストックを前倒して別のものを書きます．

想定解法

「値の差分表現」とよばれる技法を使うのが想定でした．これはリンク・カット木の実装の際によく使われるもので，たとえば以下の資料にかいてあります．

• http://planarity.org/Klein_splay_trees_and_link-cut_trees.pdf
• http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/lecture-notes/lec8.pdf

平衡二分探索木（挿入・削除がない場合は，区分木でOK）を使います．ノードにもたせる値を

struct Node {
  Node *ch[2];
  int δcost;
  int δmin;
};

のようにします．ここでδcost が値の差分表現と呼ばれるもので，本来のノードのもつ値が根までのδcostの経路和になるように定めます： cost(u) = Σ[v=n～root] δcost(v) ．区間への値の足しこみは，δcostに値を加えれば，そこを経路としてもつ点すべてに値をくわえたことになります．cost(u) の取得は，経路を手繰りながら値を足していきます．

δmin は，そのノード以下の最小値 min(u) に対して min(u) = δmin(u) - cost(u) となるように定めます．min(u) = min { cost(u), min(left), min(right) } の関係式に δmin の定義を入れると δminの更新式が得られます：δmin(u) = min { 0, δmin(left)+δcost(u), δmin(right)+δcost(u) （符号は定義の仕方でいろいろ），あとは，これにしたがって更新していくだけです．

平衡二分探索木の回転が問題で，δcost の更新に工夫が要ります．回転時に関わるノードについて，回転前後で cost(u) 不変の条件から δcost の更新式が得られるので，それにしたがって更新します．

別解法

冒頭で述べた問題に対する講評を見ると，こちらの解法が主流のようで，実際，実装も容易なので紹介します．一言でいえば，addクエリを遅延評価します．

二分木のノード u 以下すべてに x を足しこむ関数は

  add(u, x) = { cost(u) += x; add(left,x); add(right,x); }

として定義できますが，これを（普通の言語で）そのまま書くと u 以下のノード数に比例した時間がかかってしまいます．しかし，実際に cost の値が必要になるまで add の伝播を遅延させれば計算量の問題がなくなります．

実際の実装では

struct Node {
  Node *ch[2];
  int cost;
  int min;
  int δcost;
};

のように，通常の値 cost, min を保持しつつ，さらに遅延評価用に差分の値 δcost を保持します．そして必要な場合だけ δcost を反映させていきます．

こちらの実装では，回転操作で悩むことがありません．関係ありそうなところのδcostをすべて評価してしまえば普通の回転と同じです．この点で差分表現を用いる解法よりも若干実装容易といえます．