ErdemT09
commented
3 years ago Approach 2-Binary Indexed Tree (Fenwick Tree)
Instead of using an array covering entire half-ranges, we can have a structure that is more flexible in terms of space.
Instead of having duplicate ranges as array elements, we can have the array split into small chunks to be summed:
Building
Here, we have parent-child structure like 7->3->1->0. It is obvious that the difference between these indices are powers of two. At 0 indexing, we can efficiently apply this by:
- Initialize the tree sum values with array values.
- For each index i: 2.1. Find its parent index = i + least significant bit of (i+1), parent index of 11 = 11 + least significant bit of(12) = 11 + 4 = 15 2.2. Add the values of bit[i] to bit[parent] Since parent indices always come after their cihldren's, we accumulate their sum. When we get to the index 3, it would already have the values of 0,1(0's value came with 1) and 2 summed.
Updating
Updating is equivalent to adding the difference of the previous value of an element. We add this new value to the given index. Then, we get its parent by summing it with its least significant bit, then add the new value to its parent's sum. We repeat this until the parent is out of bounds of the array.,
Summing
Something to be noted is that getting range sums is equivalent to subtracting one prefix sum from another. In this case, we can get to the previous sum range by subtracting the least significant bit. To get the prefix sum of 5, we first directly get its sum. To move back to the previous range, we subtract its successor's least significant bit from it to get to 3. We add 3 and repeat. After adding 3, subtracting the bit would result in a negative number, meaning that there are no ranges before. Same happens with 7 too, trying to subtract 8 from it results in -1. After getting the two prefix sums this way, we return their difference.
Note: In implementation, we get the least significant bit of the successor of a number because of 0 indexing,. In 1-indexing, we would directly get the least significant bit of the number.
altay9
Problem: https://leetcode.com/problems/range-sum-query-mutable/
Here, the problem we face when we try to sum ranges using brute force range summing is that we cannot use prefix sums. If the range was immutable, it would have been a well choice. But reacting to the updates with prefix sums itself would have been inefficient. There are few ways of resolving this inconsistency between partial array sums and update/sum queries:
Approach 1-Segment Trees
We could think of the range sums as a tree to some degree. The root of the tree has the value
sum[0:length-1] = sum[0:mid]+sum[mid+1:length-1]. Thus, each node in this range tree has a value equal to the sum of its 2 children. For the base case in the leaves of the tree, the value would be equal tosum[i:i] = arr[i]. Above the base case, for example at the node with the range 0:1, the value would be equal to the sum of the values of the children= sum[0:0] + sum[1:1]. Thus, after calculating the values of a node's children, we can calculate the nodes value.We can naturally implement this using custom classes and such, but that is inefficient. A more efficient implementation can be done through arrays.
Build
Let's say that the root of the tree is located at the index 1. Then we can create a level-order tree where the next 2 indices are the children of the root at index 1, i.e. 2=left child, 3=right child. From this, we can infer that the second half of the tree array will consist of the base case values of individual indices. After defining these values, to continue building up in a bottom-up manner, we start at the index before the half, and the values as
tree[i] = tree[2*i] + tree[2*+1], 2*i = left child, 2*i+1 right child. Fortree[], we naturally need an array of size2*n(n=array length).Range Sum Queries
Let
ibe the left index of the query,jthe right. Initially, we must addnto both i and j because their base cases are locatednindices after their original array locations.From the building of the tree array, we know that left children are located at even indices and right children at odds. This has two implications for i and j:
-- For
i: If i is an even number, that means that we need to add the sum of its parent, not just the individual node's. If i is an odd number, that means that the value of the left child should be excluded, we only add the right child's value. In the 1. case, we simply shift i to its parent index by dividing it by 2. In the 2. case, we add the right child's value. We then increment i. This would get us to the left node of the right sibling of the parent, whose value could be entirely add ifi≤j.-- For
j: Likewise, if j is an odd number, that means that the node is a right child and the parent's range is included to be added. If j is an even number, this implies that the right child's value needs to be excluded. The procedure is symmetrical to the one done fori: In the 1. case, we shift j to the parent index by dividing by 2 (integer division). In the 2. case, we add the left child's value. We then decrement i. This would get us to the right node of the left sibling of the parent, whose value could be entirely add ifi≤j.We do these 2 procedure together.
Update Queries
This is pretty simple too. We first set tree[i+n] to the value, then update its parents values: tree[i/2] = tree[i] + tree[i^1]. The xor operation is a shortcut for using the left child if i is the right, or the right child if i is the left.