エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Fenwick Treeの定数倍高速化 - よすぽの日記
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Fenwick Treeの定数倍高速化 - よすぽの日記
Fenwick Treeの定数倍高速化 この記事はrogy advent calenderの3日目の記事です。 日本時間では4日にな... Fenwick Treeの定数倍高速化 この記事はrogy advent calenderの3日目の記事です。 日本時間では4日になっているような気がしますが、地球上にはまだ3日の部分が残っているのでセーフです。 (本当は丁寧に書くつもりだったのですが、時間がないので、プロコンをしている人向けの記事になりました。悲しいね) 概要 Fenwick Treeというデータ構造があります、これを高速化しようと頑張りました Fenwick Treeって? 調べればたくさん説明は出てくると思います。 数列について、 値の変更 区間の合計 という操作が、どちらもO(logN)で出来るデータ構造です。 例えば普通に配列でやると、O(1) / O(N)、累積和を用いると O(N) / O(1) になります。 高速化 template<class T> struct Fenwick { int N; vect