naoya https://blog.hatena.ne.jp/naoya/ naoyaのはてなダイアリー https://naoya-2.hatenadiary.org/ 圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。Binary Indexed Tree (BIT, P.… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnaoya-2.hatenadiary.org%2Fentry%2F20090606%2F1244284915" title=" Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-06-06 19:41:55 rich https://naoya-2.hatenadiary.org/entry/20090606/1244284915 1.0 100%