![](https://cdn-ak-scissors.b.st-hatena.com/image/square/d8e1594b77971c3c401328157721677668753617/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-9f5428127621718a910c8b63951390ad.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTkxNiZoPTMzNiZ0eHQ9RmVud2ljayUyMFRyZWUlMjAlRTMlODElQUUlRTYlOTUlQjQlRTclOTAlODYmdHh0LWNvbG9yPSUyMzIxMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT01NiZ0eHQtY2xpcD1lbGxpcHNpcyZ0eHQtYWxpZ249bGVmdCUyQ3RvcCZzPThiYmM3MmQ2MTRlZTcyNDIwM2JlODZjMjM3NjQ2ZjJh%26mark-x%3D142%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTcxNiZ0eHQ9JTQwa2Vuamkta29uZG8mdHh0LWNvbG9yPSUyMzIxMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT0zMiZ0eHQtYWxpZ249bGVmdCUyQ3RvcCZzPTJjYzRmMjNmNTM1NzA3MThjOGQ0ZjZmNDExNDY0ZjM3%26blend-x%3D142%26blend-y%3D491%26blend-mode%3Dnormal%26s%3D7661fa53212560134b792fec10b61c58)
エントリーの編集
![loading...](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/common/loading@2x.gif)
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
![アプリのスクリーンショット](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/entry/app-screenshot.png)
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Fenwick Tree の整理 - Qiita
概要 Fenwick Tree がよくわからなかったので自分の言葉で整理する。 問題意識 配列 A の index 0 から ... 概要 Fenwick Tree がよくわからなかったので自分の言葉で整理する。 問題意識 配列 A の index 0 から i にそれぞれ対応する value の和を計算したい。 素朴な方法に、配列全ての value を見て足し合わせる、というものがある。このとき A の長さを N とするならば、この方法の時間計算量は $O(N)$ と見て良い。 もう一つの方法に、予め配列 A の index 0 から j までの和を計算しておいたものを、新たな配列 S に格納しておく、というものがある。つまり配列 S は $$ S[j] = \sum_{i=0}^{j} A[i] $$ ということ。この方法ならば、 S[i] の要素にアクセスするだけの時間だけを考えればいいから、時間計算量は $O(1)$ とみなせる。 ここでさらに、配列 A の要素をアップデートすることを考える。例えば、 A[i]