noshi91のメモ

データ構造のある風景

2020-10-26から1日間の記事一覧

Range Mode Query 空間 Θ(n) 構築 Θ(n√n) クエリ Θ(√n)

概要 Range Mode Query - data-structures これをもう少しだけ詳しめに解説します。 面白いので好きなアルゴリズムです。 アルゴリズム まずは平方分割して、ブロックの境界を端点とする区間 ( 個ある) の全てについて最頻値とその頻度を計算します。 他にも…