Range update which is commonly asked in current Online assessment. and many interviews.

Identification:

Updating some ranges in the array but it is written that we only compute the final result at last.

Don’t get confused between when to apply segment tree or binary index tree because it is only applied when when continuously wants the result.

Difference:

Segment Tree or Binary Index Query:

update(l,r)

sum(l,r)

update(l,r)

Range Things is used only when:

update(l,r)

update(l,r)

update(l,r)

sum()

all array or some range

Steps:

1. add the number or whatever statement is written performed on the left index and reverse operation performed on the right index + 1 if right index +1 is not exceeding the range.
2. loop for all the query statement written and merge both prefix sum and original array.

for more information see the example below-

eg.

array given: [1,2,3,1,2,7]

take empty array of size same as given array size→ [0,0,0,0,0,0]

• add 4 from index 1 to 3
• add 3 from index 2 to 5

all of the operation will be done on prefix array

and then prefix array and original array gets added to yield the final result.

Steps:

1. add the number or whatever statement is written performed on the left index and reverse operation performed on the right index + 1 if right index +1 is not exceeding the range.
2. loop for all the query statement written and merge both prefix sum and original array.

for more information see the example below-

eg

1st step →

1st query = add 4 from index 1 to 3

[0,0,0,0,0,0] → prefix array

add 4 to left index and subtract it from right_index+1 → array becomes ⇒ [4,0,0,-4,0,0]

2nd query = add 3 from index 2 to 5

[4,0,0,-4,0,0] → prefix array

(since we are following 0 based indexing)

add 3 to index 1 and subtract it from 5 → array becomes ⇒ [4,3,0,-4,-3,0]

(since we are following 0 based indexing)

2nd step -

after performing all the query operation calculate the prefix sum.

for i =1 to n

prefix_sum[i] = prefix_sum[i-1]+prefix_sum[i]

prefix sum array = [4,7,7,3,0,0]

3rd step -

add both prefix sum array and final array

so final_array = [1,2,3,1,2,7] + [4,7,7,3,0,0]

Resultant array : [5,9,10,4,2,7]

Time Complexity O(n)

Space Complexity : O(n)

Eg :Question

Description

Assume you have an array of length n initialized with all 0's and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Given:
length = 5,
updates =
[
[1,  3,  2],
[2,  4,  3],
[0,  2, -2]
]
return [-2, 0, 3, 5, 3]

Explanation:
Initial state:
[ 0, 0, 0, 0, 0 ]
After applying operation [1, 3, 2]:
[ 0, 2, 2, 2, 0 ]
After applying operation [2, 4, 3]:
[ 0, 2, 5, 5, 3 ]
After applying operation [0, 2, -2]:
[-2, 0, 3, 5, 3 ]

BRUTE FORCE:

vector<int> getModifiedArray(int length, vector<vector<int>> &updates) {
        vector<int>dp(length,0);
        for(int i=0;i<updates.size();i++)
        {
            int left = updates[i][0];
            int right = updates[i][1];
            int value = updates[i][2];
            for(int j=left;j<=right;j++)
            {
                dp[j]+=value;
            }
        }
        return dp;
    }

Optimal Approach

vector<int> getModifiedArray(int length, vector<vector<int>> &updates) {
        vector<int>dp(length,0);
        for(int i=0;i<updates.size();i++)
        {
            int left = updates[i][0];
            int right = updates[i][1];
            int value = updates[i][2];
            dp[left]+=value;
            if(right+1<length)
            {
                dp[right+1]-=value;
            }
        }
        for(int i=1;i<length;i++)
        {
            dp[i]+=dp[i-1];
        }
        return dp;
    }