k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など - Qiita

はじめに ビックデータという言葉が流行ってから数年の歳月が経ち、耳にする機会が大分減ってしまいましたが、現在も大規模データを高速に処理していくことは様々な現場で重要な課題となっています。 今回はその一端として、以下の操作を高速に実現するデータ構造について特集します: 集合に要素 $v$ を挿入する 集合から要素 $v$ を削除する 集合に含まれる $k$ 番目に小さな値を取得する 「挿入」や「削除」を行えるデータ構造というと**リストが真っ先に思い浮かびますが、「$k$ 番目に小さな値を求めよ」と言われると一気に難易度が上がります。ついつい平衡二分探索木を使いたくなるのですが、BIT** や priority_queue で対応できるケースも多いです。BIT や平衡二分探索木の詳細についてはとてもよい資料が多数あるので以下に示します。 BIT BIT については hos さんの資料 Bin