フェニック木（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 投稿