セグメントツリーってすごいですよね!原理はシンプルでありながらも驚くほどの汎用性を持ち、 「区間の最小値」みたいな典型問題はもちろん、DPの漸化式に放り込んでみたり、結合法則が成り立つ構造体を入れてみたり、 果てには集合の簡易的な表現に使ってみたりと、競プロerの生活に欠かせないデータ構造です。 (筆者も先日のPCK予選で2回ほどお世話になりました) 今回はこのセグメントツリーと同様に有名な、でも標準ライブラリに実装されている機能で普段事足りているから実装したことがない人も多いかも?という 「平衡二分木」をセグメントツリーに載せてみたいと思います!でもその前に、少し予習をしておきましょう プログラミングコンテストでのデータ構造 プログラミングコンテストでのデータ構造 2 ~平衡二分探索木編~ 2つともiwi先生のスライドで、一つ目は後半にセグメントツリーの説明が、2つ目はまるまるtreap
![セグ木に平衡二分木を載せよう! - とりになりたいかものはし](https://cdn-ak-scissors.b.st-hatena.com/image/square/881b5a0b2304e2d24315e57260ca16971169559a/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fp%2Fplatypus999%2F20170920%2F20170920212445.jpg)