Range Sum Query - Mutable

The idea is to iterate through each subarray to find the sum.

For the update query, simply update the value at the given index.

For the sum query, iterate through the given subarray and add all the given indices.

The steps are as follows:

Update(‘IND’, ‘VAL’):

• Make the ‘IND’ index of the array ‘ARR’ equal to ‘VAL’.

SUM_OF_RANGE(‘l’, ‘r’):

• Initialize an integer sum equal to 0.
• Iterate from ‘i’ = ‘l’ to ‘r’:
  • Add the value of ARR[i] to ‘SUM’.
• Return the integer ‘SUM’.

The idea is to divide the given array into blocks of the size square root of ‘N’, where ‘N’ is the size of the given array. The number of elements in each block is the square root of ‘N’ and the number of blocks is equal to the square root of ‘N’. This technique is known as square root decomposition.

For the queries,

Define a class ‘SQRT_DECOMPOSITION':

1. Pre-processing:

• Store square root of ‘N’ in a double variable ‘l’, ‘N’ is the number of elements in the given array.
• Find the number of blocks by taking the ceiling of (N/l) and store in a variable 'NUMBER_OF_BLOCKS'.
• Declare an array 'BLOCKS' of size 'NUMBER_OF_BLOCKS'.
• Iterate over all the elements of the array 'ARR':
  • Find which block the current element belongs to( i.e.  i/NUMBER_OF_BLOCKS).
  • Add the elements to their respective blocks.

1. Update('IND', 'VAL'):

• Find which block the current element belongs to( ie. i/NUMBER_OF_BLOCKS) and store it in a variable ‘THIS_BLOCK’.
• Subtract ARR[index] from the block and add 'VAL' to the block.
• Make ARR[ind] equal to val.

1.  SUM_OF_RANGE(‘l’, ‘r’):

• Initialize a variable 'SUM' equals 0.
• Check the block in which the leftmost index(START_BLOCK = l/NUMBER_OF_BLOCKS) and the rightmost index(END_BLOCK = r/NUMBER_OF_BLOCKS) of the range lie.
• If the left block and the right block are the same, then iterate over from ‘l’ to ‘r’ and find the sum.
• Otherwise, iterate from ‘l’ to the end of that block and add the values to the sum. Then add all the blocks which are completely present in the range. Finally, Iterate from (END_BLOCK * NUMBER_OF_BLOCKS) to the ‘r’ index and add to the sum.

The idea is to pre-process the given array and break it down and represent it in the form of a tree.

For the update query, a subtree of the tree will be modified.

For the sum query, we will iterate over the subtrees and the sum will be calculated.

The data structure which provides these functionalities is known as a segment tree. It is also used for a number of queries like finding the minimum, maximum, GCD, etc in log(N) time.

How to create the segment tree?

The segment tree is represented in the form of an array. Each node contains information answers for a range or subarray. For any index ‘i’(not a leaf node), its children are at index 2*i and 2*i + 1 respectively.

For the queries,

Define a class segment tree:

1. Build Segment tree/ Pre-processing:

Declare an array segmentTree of size 4*N as 4*N size is enough to store all the nodes. 

The bottom-up approach is used to build a segment tree. An iterative approach can also be used but generally, the bottom-up approach is used. It takes O(N) time.

Define a recursive function 'BUILD_SEGMENT_TREE', that takes 3 arguments - 'CURRENT_INDEX', 'LOW', 'HIGH' that denotes the index at which we are storing the sum of the range 'LOW' to 'HIGH', and 'LOW' and 'HIGH' are the ranges of the indexes of the current subtree respectively.

The steps are as follows:

• Base Condition is when low and high indexes are the same and are not out of bounds, then make the segmentTree[CURRENT_INDEX] equal to arr[l].
• Find the middle 'MID' of 'LOW' and 'HIGH' as the average of 'LOW' and 'HIGH'.
• Recursively call 'BUILD_SEGMENT_TREE' for the left subtree.i.e buildSegmentTree(CURRENT_INDEX*2,LOW,MID)
• Recursively call 'BUILD_SEGMENT_TREE' for the right subtree.i.e buildSegmentTree(CURRENT_INDEX*2+1,mid+1,high)
• When it comes out of the recursive call, fill 'INDEX' index of segmentTree as the sum of its children - segmentTree[2*index] + segmentTree[2*index + 1].

1. Update Segment Tree:

Define a function 'UPDATE_SEGMENT_TREE' that takes 5 arguments - 'INDEX', 'VAL', 'CURRENT_INDEX', 'LOW', and 'HIGH', that denotes the index to update, value to update in the index, the current node of the tree, and 'LOW' and 'HIGH' are the ranges of the indexes of the current subtree respectively which returns an integer value for the index 'INDEX'.

The steps are as follows:

• Base Condition is when low, high and index are equal, it means that this is the index to update, update the value of segmentTree[CURRENT_INDEX] to 'VAL' and return.
• Find the middle 'MID' of 'LOW' and 'HIGH' as the average of ‘l’ and ‘h’.
• If 'INDEX' is smaller or equal to 'MID', then return the recursive call for the left subtree(ie. updateSegmentTree(index, VAL, CURRENT_INDEX*2, low, mid) .Make the segmentTree[CURRENT_INDEX] as the sum of the returned value and value of the right child-node.
• Otherwise, then return the recursive call for the right subtree(ie. updateSegmentTree(index, val, CURRENT_INDEX*2, mid+1, high) .Make the segmentTree[CURRENT_INDEX] as the sum of the returned value and value of the left child-node.

1. Range Sum query:

Define a function FIND_SUM_OF_RANGE that takes five arguments - 'INDEX', 'LOW', 'HIGH', ‘REQUIEDL’, ‘REQUIEDH’ which denotes the current index, lowest and highest index of the current subtree, and lowest and highest index for the range sum.

The steps are as follows:

• If ‘REQUIEDL’ is greater than 'HIGH' or ‘REQUIEDH’ is less than 'LOW', return 0 as there is no element in this range.
• Else If ‘REQUIEDL’ is less than or equal to 'LOW' and ‘REQUIEDH’ is less than or equal to 'HIGH', then return the value of the current node as the answer as it comes inside the required range.
• Else return the sum for the left and the right subtree ie. FIND_SUM_OF_RANGE(INDEX*2, LOW, MID, REQUIEDL, REQUIEDH) + FIND_SUM_OF_RANGE(INDEX*2 + 1, MID+1, HIGH, REQUIEDL, REQUIEDH).