微分積分学の基本定理型の包除原理
概要
微分積分学の基本定理型の包除原理とは、半開区間に対する関数 $g$ の計算において等式 $g [a, b) = g [0, b) - g [0, a)$ を利用するテクのこと。
微分積分学の基本定理との関連
微分積分学の基本定理とは、次のような定理であった:
$f$ を閉区間 $[a, b]$ 上で定義される連続な実数値関数とする。 $F$ を $f$ のある原始関数とする。 このとき \(\int _ a ^ b f(x) dx = F(b) - F(a)\) が成り立つ。
ある値 $g [a, b) = \sum _ {i = a} ^ {b - 1} f(i)$ である関数 $f$ があるとする。 $F(b) = g [0, b)$ とする。 するとこのテクは \(\sum _ {i = a} ^ {b - 1} f(i) = F(b) - F(a)\) という式を利用していることになる。 また、このような $f$ が存在することは等式 $g [a, b) = g [0, b) - g [0, a)$ が成り立つことの十分条件であり、かつほとんど必要条件である。
何が嬉しいのか
実装のテクとしてもアルゴリズムの一部としてもよく使われるテクであるので、手法としての新しさはない。 しかし名前が付けられていなかった (少なくとも、探しても出てこなかった)。 そのようなものに名前を付けることは、思考の整理や知識の伝達の際に有用である。
具体例
実装の簡単化のため
例えば次のような問題を考える:
$a$ 以上 $b$ 未満の非負整数であって、その $10$ 進数展開が数字 $3$ を含むようなものの数を数えよ。
これは、次のような問題を $2$ 回解くものと考えた方が楽である:
$0$ 以上 $b$ 未満の非負整数であって、その $10$ 進数展開が数字 $3$ を含むようなものの数を数えよ。
累積和や binary indexed tree の原理として
単純な累積和や binary indexed tree では、左端が $0$ の区間 $[0, b)$ に対する和 $g [0, b) = \sum _ {i = 0} ^ {b - 1} f(i)$ しか計算できない。 しかし演算が逆演算を持てば、左端が $a \ne 0$ の区間についても $g [a, b) = g [0, b) - g [0, a)$ として計算できる。
一般には逆演算はないが左端が $0$ の場合に限っては可能である、といった場合が存在しうることには注意したい。
区間更新に対して用いる
区間の点の総和を求めるのでなく、区間の各点に対する操作を行なうことも考えられる。 これは双対セグメント木という形でなされるものと同様である。
特に、imos法は始点を $+ \infty$ としてこれを用いたものと見ることができる。
木上のパスに対して用いる
次のような問題を考える:
頂点に非負整数の重みのついた木が与えられる。次のようなクエリがたくさん与えらるので処理せよ:
- この木の頂点の対が与えられる。その間のパス上の頂点の重みを考え、それらすべての和を答えよ。
- この木の頂点の対が与えられる。その間のパス上の頂点の重みを考え、それらすべての排他的論理和を答えよ。
勝手に根を固定することにより、これらのクエリはこのテクで処理できる。 通常は最小共通祖先 (LCA) も求める必要がある。 排他的論理和のように冪零性があれば LCA は不要である。
なお、最大値などの逆演算がない場合は重軽分解をしてセグメント木にのせる必要がある。