Parallel Binary Search（並列二分探索）による効率的なクエリ処理
並列二分探索の基本概念
通常の二分探索は単一の値に対して適用されますが、複数のクエリに対して個別に二分探索を行うと計算量が爆発します。並列二分探索（Parallel Binary Search / 整体二分）は、複数のクエリを同時に処理することでこの問題を解決するオフラインアルゴリズムです。
核心的なアイデアは、すべてのクエリの探索範囲を値域 [low, high] とし、定義域 [L ...
8月8日 04:16 投稿
フェニック木（Binary Indexed Tree）の基礎と応用
フェニック木（Binary Indexed Tree, BIT）は、主に数列の prefix sum（接頭辞和）を効率的に管理・計算するために設計されたデータ構造です。セグメント木と比較して実装が簡潔であり、定数倍の計算コストが低いため、頻繁な更新とクエリが発生する箇所で広く利用されています。本記事では、基本的な1次元の構造から、差分を利用した区間更新、および2次元への拡張につい ...
7月11日 16:07 投稿
数論的計算と平方分割を用いた競技プログラミング問題の解説
問題 1：数論的和の計算
この問題では、大きな指数を持つべき乗の和を特定の素数で割った余りを求める必要がある。 naive な快速幂を用いた計算では $O(\sqrt{m} \cdot \log n)$ となり、制限時間を超えてしまう。ここで、法となる数が小さくかつ素数であることに注目する。
フェルマの小定理より、指数部分は法 $p$ に対して $p-1$ で割った余りとして扱ってよい。これに ...
6月1日 04:20 投稿