さわって味わうフェニック木

スタイリィにてモバイルアプリ開発・サーバサイド開発・植物の世話などをやっている河田です。

さて、技術ブログを期待されている方はもしいらしたら大変恐縮ですが、今回は昨日勉強したばかりのニワカ知識を得意げにひけらかすことにします。

お題は↑です。
数列の部分和を求めるためのデータ構造ですが、部分和の計算がちょっと遅くなるかわりに、途中で数列の要素を変更してもそれほど遅くならない、というものです。
詳細な説明はリンク先などでご覧ください。私には荷が重いです。

じゃここには何を書くのかというと、Vue.jsの練習を兼ねて、フェニック木の構造をさわって理解するためのアプリ的ななんかを書いてみましたので、その説明です:
https://s3-ap-northeast-1.amazonaws.com/techblog.stily.co.jp/kawada_bit/index.html#/15
(末尾の数字を変えてリロードするとサイズが変わりますが、見た目がバグると思います)

上側(列インデックス)の数字は「元の数列」の要素の番号に対応し、
左側(行インデックス)の数字はフェニック木のノードの番号に対応します
(どちらも1から始めることに注意)。

背景色がオレンジ色のセルは、その位置のフェニック木のノードが、元の数列のどの部分和を持っているのかを表します。
(例)
6行目を見ると、5列目と6列目のセルがオレンジ色になっている。
→ 6番目のノードは、元の数列の5番目と6番目の和を持っている。

どこか適当にオレンジ色のセルをポイントすると、↑のように一部が緑色に変わります。
これは、ポイントした位置のノードの代々の親ノードを示しています。
↑の画像は13番目のノードをポイントした時のものです。
ノート13(=0b1101)の親はノード12(=0b1100)、そしてノード12の親はノード8(=0b1000)なので、これらが緑色になっています。なおノード8には親はありません(強いて言えばノード0が親)。
元の数列について、13番目までの要素の和を求めたい場合は、まずノード13、次にノード12、最後にノード8の中身を見て、それらを足し合わせればOKです。

さて、ボタン"Add"を押すと、部分和モードから更新モードに切り替わります。
この状態で適当にオレンジのセルをポイントすると

こうなります。
この画像は、元の数列の9番目の要素を変更した時、フェニック木のノード9、ノード10、およびノード12に影響が及ぶことを示しています。
(サイズがもっと大きければ、さらにノード16, 32, 64... と波及します。)
つまり、これらが更新されるべきノードということになります。

最後に、本体部分のVueコンポーネントファイルの中身を置いておきます。
<center>などという文字列が見えますね・・・

<!-- BIT.vue -->
<template>
    <div class="mybit">
        <center>
            <h3>BIT / Fenwick Tree (n = {{ n }})</h3>
            <div class="buttons">
                <button id="sum" @click="flip('sum')">Sum</button>
                <button id="add" @click="flip('add')">Add</button>
            </div>
            <table id="main">
                <tr>
                    <td></td>
                    <td v-for="i in nums" :key=i v-bind:class="'num num_'+i">
                        <span>{{ i }}</span>
                    </td>
                </tr>
                <tr v-for="i in nums" :key=i>
                    <td v-bind:class="'num num_'+i">{{ i }}</td>
                    <td v-for="j in leadings(i)" :key=j v-bind:class="'leading row_'+i+' col_'+j">
                        <span></span>
                    </td>
                    <td v-for="j in bodies(i)" :key=j 
                        v-bind:class="'body body_'+i+' row_'+i+' col_'+j"
                        @mouseover="light(i)"
                        >
                        <span>{{ i == j ? "●" : ""}}</span>
                    </td>
                    <td v-for="j in trailings(i)" :key=j v-bind:class="'trailing row_'+i+' col_'+j">
                        <span></span>
                    </td>
                </tr>
            </table>
        </center>
    </div>
</template>

<script>
export default {
    name: 'BIT',
    data () {
        return {
            n: undefined,
            mode: "sum",
        }
    },
    computed: {
        nums: function() { return _.range(0, 1+this.n) }
    },
    methods: {
        flip: function(mode) {
            this.mode = mode
            if (mode == "sum") {
                document.getElementById("sum").classList.add("on")
                document.getElementById("add").classList.remove("on")
            } else {
                document.getElementById("sum").classList.remove("on")
                document.getElementById("add").classList.add("on")
            }
            this.light()
        },

        leadings:  function(k) { return _.range(0, k-(k&(-k))+1) },
        bodies:    function(k) { return _.range(k-(k&(-k))+1, k+1) },
        trailings: function(k) { return _.range(k+1, this.n+1) },

        light: function(k) {
            _(document.getElementsByTagName('td')).each(e => {
                e.classList.remove('active')
                e.classList.remove('on')
            })
            if (!k) { return }
            switch (this.mode) {
            case "sum":
                while (0 < k) {
                    _(document.getElementsByClassName("body_"+k)).each(e => e.classList.add('on'))
                    _(document.getElementsByClassName("num_"+k)).each(e => e.classList.add('on'))
                    k = k - (k&(-k))
                }
                break
            case "add":
                _(document.getElementsByClassName("col_"+k)).each(e => e.classList.add('active'))
                while (0 < k && k <= this.n) {
                    _(document.getElementsByClassName("body_"+k)).each(e => e.classList.add('on'))
                    _(document.getElementsByClassName("num_"+k)).each(e => e.classList.add('on'))
                    k = k + (k&(-k))
                }
                break
            }
        },
    },
    created: function() {
        this.n = parseInt(this.$route.params.n || 36)
    },
    mounted: function() {
        this.flip("sum")
    }
}
</script>

<style>
.mybit {
    text-align: center;
}
.buttons {
    margin-bottom: 10px;
}
button.on {
    font-weight: bold;
    background-color: lightgreen;
}
table {
    border-collapse: collapse;
}
td {
    width: 20px; height: 20px;
    text-align: center;
}
td.num { padding: 0; }
td:not(.num) {
    padding: 1px;
}
td > span {
    display: block;
    width: 100%; height: 100%;
}
td:first-child {
    border-right: 1px solid #aaa;
}
tr:first-child td {
    border-bottom: 1px solid #aaa;
}
td.body {
    color: white;
}
td.body > span {
    background-color: orange;    
}
td.active > span {
    background-color: #ddd;    
}
td.on > span {
    background-color: lightgreen !important;
}
</style>

おしまい。

[追記]
行と列を入れ替えて、横幅をスリムにしたバージョンを作りました。仕事しろ。
https://s3-ap-northeast-1.amazonaws.com/techblog.stily.co.jp/kawada_bit2/index.html#/200
サイズを大きくしてもデザインが破綻しにくいので、多少楽しめます。