bit.html

<h1 id="binary-indexed-trees-and-segment-trees">Binary Indexed Trees and Segment Trees</h1>
<h2 id="the-problem">The Problem</h2>
<p>We want to have a data structure that allows us to do two things</p>
<ol>
<li>Make queries of the form <code>f(a[i], ..., a[j])</code> for <code>i &lt;= j</code> (the <strong>query</strong>)</li>
<li>Update <code>a[i] = v</code> for some <code>i</code> (the <strong>update</strong>)</li>
</ol>
<p>Naively, one could do this in such a way that either the query or the update is <code>O(1)</code> and the other is <code>O(n)</code>. The most basic method would be to simply store <code>a[i]</code> and then for the query, simply compute the function in <code>O(n)</code>. However, that will obviously not be good enough for practical applications. </p>
<h2 id="segment-trees">Segment Trees</h2>
<p>Segment trees provide a way to efficiently and easily perform both the query and the update in <code>O(log n)</code>. The key to how this works is that the cumulative totals are stored in a tree so that when the query is performed, the query only needs to traverse the limited number of subtotals to get the overall total.</p>
<h3 id="update">Update</h3>
<p>To achieve the update with a segment tree, first the leaf element corresponding to the array is updated. Then, this update propagates up the tree. The parent node of the current is updated based on the function applied to its two children. Then, the current becomes the parent and the parent moves up.</p>
<div class="animation-box" id="updater">
<p>Click node to update:<input type="text" id="updateValue" placeholder="Value" /></p>
</div>

<h3 id="downward-join">Downward join</h3>
<p>Selecting arbitrary ranges in the array is pretty complicated. It&#39;s much easier to understand how the process works for a range where the index <code>x &lt;= j</code>. This process works by looking at any given leaf as the current. Two things can happen</p>
<ol>
<li><p>The current is the right child of its parent.</p>
<p> We want to get the function of everything to the left of the original index. We know that the parent contains the total function of all of its children. Because we are at the right child, we want to include the left child in our calculations. Because the parent contains both the right child and the left child, we can just move the pointer to the parent node and continue.</p>
</li>
<li><p>The current is the left child of its parent</p>
<p> We do not want to include the right child in our calculations, so we cannot use the parent of the current node. However, we want to include all of the nodes below the current node. Thus, we want to include the next adjacent sibling of the parent. This becomes our next node</p>
</li>
</ol>
<p>As we move along the tree, we perform the function on the value at each node with the previous subtotal. When we can no longer move to the next node, we are finished and we have created the total of the range.</p>
<div class="animation-box" id="leftsum"></div>

<h3 id="upward-join">Upward join</h3>
<p>The process for indices <code>x &gt;= i</code> is similar with the role of the left and right child reversed.</p>
<div class="animation-box" id="rightsum"></div>

<h3 id="middle-join">Middle join</h3>
<p>For selecting a range <code>i &lt;= x &lt;= j</code> we can do a process that is very similar to the above, except we do both at the same time, necessitating two pointers. Instead of stopping when there is no further node to process, this iteration stops when the two pointers cross. If</p>
<ol>
<li><p>If the pointers point to the same node, then this node should be included. Then the iteration terminates</p>
</li>
<li><p>If the pointers point to nodes such that the right pointer points to a node to the left of the left pointer, then the iteration is finished. These two new nodes should not be included in the total.</p>
</li>
</ol>
<div class="animation-box" id="middlesum"></div>

<h2 id="binary-indexed-tree">Binary Indexed Tree</h2>
<p>Binary indexed trees are simply segment trees generalized to take up less space. To be able to do this, binary indexed trees make use of the inverse property of certain functions. For that reason, they are only suitable for functions with an inverse, like addition (subtraction) or multiplication (division).</p>
<p>Binary indexed trees use this property to remove all of the right children of nodes. Because the function has an inverse, the right child can be figured out by <code>right = finv(parent, left)</code>. Then the nodes can simply be flattened into an array.</p>
<div class="animation-box" id="flatten"></div>

<h3 id="downward-join">Downward join</h3>
<p>For the downwards join, the algorithm proceeds exactly the same way as with a segment tree, except when there is a right child, the algorithm automatically skips to the parent because the right child does not exist. Because of the way we have numbered the nodes finding the next node is very easy. Which parent nodes have been summed is encoded in the binary representation of the current index.</p>
<p>Thus, we simply get the lowest set bit (proving how the follow code works is left as an exercise to the reader). The next parent to sum is found at the ind with this bit cleared.</p>
<pre><code>bit = ind &amp; -ind
new_ind = ind - bit</code></pre>
<div class="animation-box" id="leftbin"></div>

<h3 id="other-joins">Other joins</h3>
<p>To join between two indices <code>i &lt;= x &lt;= j</code>, simply do the downwards join of the upper index <code>j</code> and take the inverse of the downwards join of one below lower index <code>i</code>.</p>
<pre><code>join = finv(join(j), join(i-1))</code></pre>
<p>This will include everything including <code>j</code>, and remove everything below <code>i</code>, excluding <code>i</code> itself from the removal.</p>
<h3 id="update">Update</h3>
<p>The other issue lies in updating the tree. Because we no longer have any right children, we are not able to use the function of the left and right children in order to update the parent.</p>
<p>The base update has changed form. Now, it changes the value by the given index instead of setting the value at the given index. To achieve the original functionality, we can do the inverse function of the current value at the given index and the value we desire to set. However, that will typically not be necessary <code>update(i, finv(new_value, query(i-1, i)))</code>.</p>
<p>For the update, instead of subtracting the lowest set bit, we add the lowest set bit.</p>
<pre><code>bit = ind &amp; -ind
new_ind = ind + bit</code></pre>
<p>This will traverse all the parent nodes in the tree and set all of the required indices. At each node, replace its value with the function of its current value and the update value. </p>
<pre><code>new_value = f(old_value, update)</code></pre>
<div class="animation-box" id="updatebin"></div>

<script src="https://rawgit.com/DmitryBaranovskiy/raphael/v2.1.2/raphael-min.js"></script>
<style type="text/css">
@media print {
    div.animation-box {
        display: none;
    }
}
div.animation-box svg text {
    pointer-events: none;
}
</style>

<script>
(function(Raphael) {
    Raphael.el.extractJSON = function extractJSON() {
        var json = {}, attr = this.attr(), key
        json.type = this.type
        for (key in attr) {
            if (attr.hasOwnProperty(key)) {
                json[key] = attr[key]
            }
        }
        return json
    }

    Raphael.st.extractJSON = function extractJSON() {
        var json = []
        this.forEach(function (el) {
            json.push(el.extractJSON())
        })
        return json
    }

    var defaultTextParams = {
        'text-anchor': 'middle'
    }
    var defaultNodeParams = {}
    var defaultLineParams = {}
    Raphael.fn.binaryTree = function binaryTree(layers, x, y, width, height, radius) {
        layers |= 0
        if (layers <= 0) return;
        var paper = this
        var out = {
            nodes: [null],
            elems: paper.set(),
            lines: paper.set(),
            texts: paper.set(),
            rows: layers
        }
        var maxRow = 1 << (layers-1)
        var yextra = height - 2*radius*layers
        var vspace = yextra/layers
        var i, j, k
        for (i=0;i<layers;++i) {
            var cy = 2*radius*i + radius + vspace*i + y + vspace/2
            var xoff = width / (1 << (i+1))
            for (j=0,k=1<<i;j<k;++j) {
                var cx = xoff*(2*j+1) + x
                var cur = {}
                cur.elem = paper.circle(cx, cy, radius).attr(defaultNodeParams)
                cur.text = paper.text(cx, cy, '').attr(defaultTextParams)
                cur.index = k+j
                cur.column = j
                cur.row = i
                var parent = out.nodes[(k + j) >> 1]
                if (parent) {
                    var edge = {}
                    var pattr = parent.elem.attr()
                    var cattr = cur.elem.attr()
                    edge.line = paper.path(['M',pattr.cx,pattr.cy,'L',cattr.cx,cattr.cy]).attr(defaultLineParams).toBack()
                    edge.node = cur
                    if (j & 1) {
                        parent.right = edge
                    } else {
                        parent.left = edge
                    }
                    cur.parent = {}
                    cur.parent.node = parent
                    cur.parent.line = edge.line

                    out.lines.push(edge.line)
                }
                out.texts.push(cur.text)
                out.nodes.push(cur)
                out.elems.push(cur.elem)
            }
        }
        return out
    }
})(Raphael)

window.onload = function() {
    var baseNode = {
        fill: '#77f',
        'stroke-width': 0,
    }
    var baseEdge = {
        'stroke-width': 2,
        stroke: '#000'
    }
    var baseText = {
        'font-size': 15
    }
    var baseBottomNode = {
        fill: '#ff7',
        'stroke-width': 0,
        stroke: '#000',
    }
    var baseDims = {
        width: 700,
        height: 300,
        rows: 5,
        radius: 20
    }
    var makeTree = function(paper, dims, identity) {
        var tree = paper.binaryTree(dims.rows, dims.x|0, dims.y|0, dims.width, dims.height, dims.radius)
        tree.elems.attr(baseNode)
        tree.lines.attr(baseEdge)
        tree.texts.attr(baseText)
        if (!!identity || identity === 0)
            tree.texts.attr('text', identity)
        return tree
    }

    var makeTreeBottomInteractive = function(tree, clickFunc) {
        var hoverAnim = Raphael.animation({
            'stroke-width': 3,
        }, 300)
        var baseAnim = Raphael.animation({
            'stroke-width': 0
        }, 300)

        var bottomLevelNodes = tree.nodes.slice(1<<(tree.rows-1),1<<tree.rows)
        bottomLevelNodes.forEach(function(node) {
            var e = node.elem
            e.attr(baseBottomNode)
            e.mouseover(function() {
                e.animate(hoverAnim)
            })
            e.mouseout(function() {
                e.animate(baseAnim)
            })
            e.click(function() {
                clickFunc(node)
            })
        })
    }

    var randomizeSegTree = function(tree, func) {
        var i
        for (i=1<<(tree.rows-1);i<tree.nodes.length;++i) {
            var value = Math.random()*15|0
            var node = tree.nodes[i]
            node.text.attr('text', value)
            while (node.parent) {
                var parent = node.parent.node
                var node2 = tree.nodes[node.index ^ 1]
                parent.text.attr('text',func(node.text.attr('text'),node2.text.attr('text')))
                node = parent
            }
        }
    }

    var upJoinColor = '#0f0'
    var downJoinColor = '#f00'

    var func = function(a, b) {
        return +a + +b
    }
    func.identity = 0

    var nextDownJoin = function(tree, node) {
        if (node.index === 1)
            return
        if (node.index & 1)
            return node.parent.node
        var parent = node.parent.node
        if (((parent.index) & (parent.index - 1)) !== 0) {
            return tree.nodes[parent.index - 1]
        }
    }

    var nextUpJoin = function(tree, node) {
        if (node.index === 1)
            return
        if ((node.index & 1) === 0)
            return node.parent.node
        var parent = node.parent.node
        if (((parent.index) & (parent.index + 1)) !== 0) {
            return tree.nodes[parent.index + 1]
        }
    }

    ;(function(Raphael) {

        var amount = document.getElementById('updateValue')

        var joinNums = function(node, func) {
            if (!node.parent)
                return
            var paper = node.elem.paper
            var node2 = tree.nodes[node.index ^ 1]
            var newValue = func(node.text.attr('text'), node2.text.attr('text'))
            var parent = node.parent.node
            var texts = paper.add([node.text.extractJSON(), node2.text.extractJSON()])
            var jx = parent.elem.attr('cx')
            var jy = node.elem.attr('cy')
            var anim = Raphael.animation({
                x: jx,
                y: jy
            }, 1000, Raphael.backIn, function animDone() {
                if (animDone.over)
                    return
                animDone.over = true
                texts.remove()
                var animText = paper.text(jx, jy, newValue).attr(baseText)
                animText.animate({
                    x: parent.elem.attr('cx'),
                    y: parent.elem.attr('cy')
                }, 1000, Raphael.linear, function() {
                    parent.text.attr('text', newValue)
                    animText.remove()
                    joinNums(parent, func)
                })
            })
            texts.animate(anim)
        }

        var doUpdate = function(node, value) {
            node.text.attr('text', +value)
            joinNums(node, func)
        }

        var beginUpdate = function(node) {
            var num = amount.value
            if (!num.length || isNaN(num)) {
                amount.focus()
                return
            }
            amount.value = ''
            doUpdate(node, num)
            amount.focus()
        }

        var dims = baseDims

        var paper = Raphael(document.getElementById('updater'), dims.width, dims.height)
        var tree = makeTree(paper, baseDims, func.identity)
        makeTreeBottomInteractive(tree, beginUpdate)

    })(Raphael)

    ;(function (Raphael){
        var dims = baseDims
        var paper = Raphael(document.getElementById('leftsum'), dims.width+30, dims.height+30)
        var tree = makeTree(paper, baseDims, func.identity)

        var moveLineAttrs = {
            stroke: downJoinColor,
            'stroke-width': 3,
            'arrow-end': 'classic'
        }

        var subtotalTextAttrs = {
            'font-size': 20,
            'fill': downJoinColor
        }

        var subtotalOffset = 10

        var traverse = function(node, subtotalText) {
            var nextNode, rightChild, nextValue
            var paper = node.elem.paper
            if (!subtotalText) {
                subtotalText = paper.text(node.elem.attr('cx') + node.elem.attr('r') + subtotalOffset, node.elem.attr('cy'), func.identity).attr(baseText)
                subtotalText.attr(subtotalTextAttrs)
            }

            nextNode = nextDownJoin(tree, node)
            nextValue = subtotalText.attr('text')
            var moveToNext
            if (!nextNode) {
                moveToNext = function() {
                    subtotalText.attr('text', nextValue).animate({opacity: 0}, 2000, Raphael.linear, function() {
                        subtotalText.remove()
                    })
                }
            } else {
                moveToNext = function() {
                    var sattr = node.elem.attr(), dattr = nextNode.elem.attr()
                    var moveLine = paper.path(['M',sattr.cx,sattr.cy,'L',dattr.cx,dattr.cy]).attr(moveLineAttrs)
                    subtotalText.animate({
                        x: dattr.cx + dattr.r + subtotalOffset,
                        y: dattr.cy
                    }, 1500, Raphael.backIn, function() {
                        moveLine.remove()
                        traverse(nextNode, subtotalText)
                    })
                }
            }  
            if (!!(node.index & 1) && !!nextNode) {
                moveToNext()
            } else {
                nextValue = func(nextValue, node.text.attr('text'))
                var nodeText = paper.add([node.text.extractJSON()]).pop()
                nodeText.animate({
                    x: subtotalText.attr('x'),
                    y: subtotalText.attr('y')
                }, 500, Raphael.backIn, function() {
                    nodeText.remove()
                    subtotalText.attr('text', nextValue)
                    moveToNext()
                })
            }
        }

        randomizeSegTree(tree, func)
        makeTreeBottomInteractive(tree, traverse)
    })(Raphael)

    ;(function (Raphael){

        var dims = baseDims
        var paper = Raphael(document.getElementById('rightsum'), dims.width+30, dims.height+30)
        var tree = makeTree(paper, baseDims, func.identity)

        var moveLineAttrs = {
            stroke: upJoinColor,
            'stroke-width': 3,
            'arrow-end': 'classic'
        }

        var subtotalTextAttrs = {
            'font-size': 20,
            'fill': upJoinColor
        }

        var subtotalOffset = 10

        var traverse = function(node, subtotalText) {
            var nextNode, leftChild, nextValue
            var paper = node.elem.paper
            if (!subtotalText) {
                subtotalText = paper.text(node.elem.attr('cx') - node.elem.attr('r') - subtotalOffset, node.elem.attr('cy'), func.identity).attr(baseText)
                subtotalText.attr(subtotalTextAttrs)
            }

            nextNode = nextUpJoin(tree, node)
            nextValue = subtotalText.attr('text')
            var moveToNext
            if (!nextNode) {
                moveToNext = function() {
                    subtotalText.attr('text', nextValue).animate({opacity: 0}, 2000, Raphael.linear, function() {
                        subtotalText.remove()
                    })
                }
            } else {
                moveToNext = function() {
                    var sattr = node.elem.attr(), dattr = nextNode.elem.attr()
                    var moveLine = paper.path(['M',sattr.cx,sattr.cy,'L',dattr.cx,dattr.cy]).attr(moveLineAttrs)
                    subtotalText.animate({
                        x: dattr.cx - dattr.r - subtotalOffset,
                        y: dattr.cy
                    }, 1500, Raphael.backIn, function() {
                        moveLine.remove()
                        traverse(nextNode, subtotalText)
                    })
                }
            }  
            if (!(node.index & 1) && !!nextNode) {
                moveToNext()
            } else {
                nextValue = func(nextValue, node.text.attr('text'))
                var nodeText = paper.add([node.text.extractJSON()]).pop()
                nodeText.animate({
                    x: subtotalText.attr('x'),
                    y: subtotalText.attr('y')
                }, 500, Raphael.backIn, function() {
                    nodeText.remove()
                    subtotalText.attr('text', nextValue)
                    moveToNext()
                })
            }
        }

        randomizeSegTree(tree, func)
        makeTreeBottomInteractive(tree, traverse)
    })(Raphael)

    ;(function (Raphael){
        var dims = baseDims
        var paper = Raphael(document.getElementById('middlesum'), dims.width+30, dims.height+30)
        var tree = makeTree(paper, baseDims, func.identity)

        var moveLineAttrs = {
            'stroke-width': 3,
            'arrow-end': 'classic'
        }

        var subtotalTextAttrs = {
            'font-size': 20
        }

        var subtotalOffset = 10

        var traverse = function(node1, node2, subtotalText1, subtotalText2) {
            var nextValue1, nextValue2, nextNode1, nextNode2
            var paper = node1.elem.paper
            var sattr1 = node1.elem.attr()
            var sattr2 = node2.elem.attr()
            if (!subtotalText1) {
                subtotalText1 = paper.text(sattr1.cx - sattr1.r - subtotalOffset, sattr1.cy, func.identity).attr(baseText)
                subtotalText1.attr(subtotalTextAttrs).attr('fill', upJoinColor)
                subtotalText2 = paper.text(sattr2.cx + sattr2.r + subtotalOffset, sattr2.cy, func.identity).attr(baseText)
                subtotalText2.attr(subtotalTextAttrs).attr('fill', downJoinColor)
            }

            nextNode1 = nextUpJoin(tree, node1)
            nextNode2 = nextDownJoin(tree, node2)
            nextValue1 = subtotalText1.attr('text')
            nextValue2 = subtotalText2.attr('text')
            var moveToNext, moveTexts

            var fadeSubtotalTexts = function me() {
                me.runs = (me.runs|0)+1
                if (me.runs === 2) {
                    moveTexts.remove()
                    subtotalText2.attr('text', nextValue2).animate({opacity: 0}, 2000, Raphael.linear, function() {
                        subtotalText2.remove()
                    })
                }
            }

            if (node1.index > node2.index) {
                nextValue2 = func(nextValue2, nextValue1)
                moveTexts = subtotalText1
                var moveTextAnim = Raphael.animation({
                    x: (subtotalText1.attr('x') + subtotalText2.attr('x'))/2,
                    y: (subtotalText1.attr('y') + subtotalText2.attr('y'))/2
                }, 1000, Raphael.backIn, fadeSubtotalTexts)
                subtotalText1.animate(moveTextAnim)
                subtotalText2.animate(moveTextAnim)
                return
            } else if (node1 === node2) {
                moveTexts = paper.add([node1.text.extractJSON()])
                nextValue2 = func(nextValue2, func(nextValue1, node1.text.attr('text')))
                moveTexts.push(subtotalText1)
                var moveTextAnim = Raphael.animation({
                    x: subtotalText2.attr('x'),
                    y: subtotalText2.attr('y')
                }, 1000, Raphael.backIn, fadeSubtotalTexts)
                moveTexts.forEach(function(el) {
                    el.animate(moveTextAnim)
                })
                return
            }
            moveToNext = function() {
                var dattr1 = nextNode1.elem.attr(), dattr2 = nextNode2.elem.attr()
                var moveLines = paper.set()

                var finishMoving = function me() {
                    me.runs = (me.runs|0)+1
                    if (me.runs === 2) {
                        moveLines.remove()
                        traverse(nextNode1, nextNode2, subtotalText1, subtotalText2)
                    }
                }
                moveLines.push(
                    paper.path(['M',sattr1.cx,sattr1.cy,'L',dattr1.cx,dattr1.cy]).attr('stroke', upJoinColor).attr(moveLineAttrs), 
                    paper.path(['M',sattr2.cx,sattr2.cy,'L',dattr2.cx,dattr2.cy]).attr('stroke', downJoinColor).attr(moveLineAttrs))
                subtotalText1.animate({
                    x: dattr1.cx - dattr1.r - subtotalOffset,
                    y: dattr1.cy
                }, 1500, Raphael.backIn, finishMoving)
                subtotalText2.animate({
                    x: dattr2.cx + dattr2.r + subtotalOffset,
                    y: dattr2.cy
                }, 1500, Raphael.backIn, finishMoving)
            }
            var join1 = !!(node1.index & 1)
            var join2 = !(node2.index & 1)
            if (join1 || join2) {
                var nodeTexts = paper.set()
                var finishAnim = function me() {
                    me.runs = (me.runs|0)+1
                    if (me.runs !== ((join1+join2)|0)) 
                        return
                    nodeTexts.remove()
                    subtotalText1.attr('text', nextValue1)
                    subtotalText2.attr('text', nextValue2)
                    moveToNext()
                }
                if (join1) {
                    nextValue1 = func(nextValue2, node1.text.attr('text'))
                    nodeTexts.push(paper.add([node1.text.extractJSON()]).pop().animate({
                        x: subtotalText1.attr('x'),
                        y: subtotalText1.attr('y')
                    }, 500, Raphael.backIn, finishAnim))
                }
                if (join2) {
                    nextValue2 = func(nextValue2, node2.text.attr('text'))
                    var nodeText = paper.add([node2.text.extractJSON()]).pop()
                    nodeText.animate({
                        x: subtotalText2.attr('x'),
                        y: subtotalText2.attr('y')
                    }, 500, Raphael.backIn, finishAnim)
                    nodeTexts.push(nodeText)
                }
            } else {
                moveToNext()
            }
        }

        var joinStart = null, joinEnd = null
        var doJoin = function doJoin(node) {
            if (!!joinStart) {
                if (node.index < joinStart.index) {
                    joinEnd = joinStart
                    joinStart = node
                } else {
                    joinEnd = node
                }
                joinEnd.elem.attr({fill: downJoinColor})
                joinStart.elem.attr({fill: upJoinColor})
                traverse(joinStart, joinEnd)
                joinStart.elem.animate(baseBottomNode, 1000)
                joinEnd.elem.animate(baseBottomNode, 1000)
                joinStart = null
                joinEnd = null
            } else {
                joinStart = node
                node.elem.attr({fill: upJoinColor})
            }
        }

        randomizeSegTree(tree, func)
        makeTreeBottomInteractive(tree, doJoin)
    })(Raphael)

    ;(function (Raphael){
        var dims = baseDims
        var paper = Raphael(document.getElementById('flatten'), dims.width+30, dims.height+30+dims.radius*2)
        var tree = makeTree(paper, baseDims)

        var disableNodeAttrs = {
            fill: '#aaf'
        }

        var disabledNodes = paper.set()

        tree.nodes.forEach(function(node) {
            if (!node)
                return
            if (!(node.index & 1) || node.index === 1) {
                node.enabled = true
                var level = tree.rows-node.row-1
                node.text.attr('text', (1<<(level))*(node.column+1))
            } else {
                disabledNodes.push(node.elem)
            }
        })
        disabledNodes.attr(disableNodeAttrs)

        var desty = dims.height + 10 + dims.radius*2
        var destxs = tree.nodes.slice(1<<(tree.rows-1), 1<<tree.rows).map(function(node) {
            return node.elem.attr('cx')
        })


    })(Raphael)
}



</script>