Segment trees

 

Segment trees are a data structure that provide a way to efficiently update make updates and queries with ranges of elements in an array. For example, suppose we want to make queries about ranges of an array and allows updating of entries. Given any associative function f, we can use segment trees to compute f(a[0], f(a[1], ..., f(a[n])...)) in O(log(n)), and we can update a[i] in O(log(n)) as well.

 

To do this, assume we have an array with n entries. For simplicity, assume n is a power of 2; otherwise we can pad it. Then we will create a binary search tree with these n elements as leaves. Each leaf with store the corresponding array value. Every node in the tree represents some range of the array. The leaves represent the entries they store, and a parent represents the union of the ranges of its two children.

 

Because we want to compute f applied to ranges, every node in the tree will store f applied to all the leaves below it. To update an array element, we only need to update it and all the values stored at the nodes above it.

 

To query f applied to a range, we want to find a set of O(log(n)) nodes in the tree representing disjoint intervals whose union is our given range. Then we can just combine the values of f on these intervals to get our value (e.g. if f is addition, we would add these stored values). However, this is easy given our tree structure. [Draw picture]

 

If we let f(x, y) = x + y it's clear that we can use segment trees to find the sum of a range in our array and update elements. However, we can instead also use segment trees in a slightly different way to add to ranges of our array and query individual elements. To do this, initialize all leaves to store the corresponding array value, and initialize all parent nodes to store 0. We will represent the value stored at a leaf as the sum of the values stored at it and all its parents. This means that if we add to the value stored at the root of some node, it effectively adds that value to the every leaf below that node.

 

We can add x to the range [i, j] recursively. A simple way to do this is by adding x to [0, j] and subtracting x from [0, i - 1]. Therefore, we only need to see how to add a value x to some range [0, i]. We can do this recursively starting at theroot of the tree. If [0, i] intersects the range represented by the right child of the root, then add x to the left child's stored value (which effectively adds it to every leaf in the left subtree) and recursively add x to [0, i] on the right child. Otherwise, just recursively add x to [0, i] on the left child.