We want to have a data structure that allows us to do two things
- Make queries of the form
f(a[i], ..., a[j])fori <= j(the query) - Update
a[i] = vfor somei(the update)
Naively, one could do this in such a way that either the query or the update is O(1) and the other is O(n). The most basic method would be to simply store a[i] and then for the query, simply compute the function in O(n). However, that will obviously not be good enough for practical applications.
Segment trees provide a way to efficiently and easily perform both the query and the update in O(log n). 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.
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.
Click node to update:
Selecting arbitrary ranges in the array is pretty complicated. It's much easier to understand how the process works for a range where the index x <= j. This process works by looking at any given leaf as the current. Two things can happen
-
The current is the right child of its parent.
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.
-
The current is the left child of its parent
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
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.
The process for indices x >= i is similar with the role of the left and right child reversed.
For selecting a range i <= x <= j 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
-
If the pointers point to the same node, then this node should be included. Then the iteration terminates
-
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.
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).
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 right = finv(parent, left). Then the nodes can simply be flattened into an array.
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.
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.
bit = ind & -ind
new_ind = ind - bit
Because the operator has an inverse, the upwards join is just the downwards join, inverted.
The middle join is the downards join of the upper limit combined with the upwards join of the lower limit.
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.
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 update(i, finv(new_value, query(i-1, i))).
For the update, instead of subtracting the lowest set bit, we add the lowest set bit.
bit = ind & -ind
new_ind = ind + bit
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.
new_value = f(old_value, update)