Print modified array after executing the commands of addition and subtraction
Given an array of size βnβ and a given set of commands of size βmβ. Every command consist of four integers q, l, r, k. These commands are of following types:
- If q = 0, add βkβ to all integers in range βaβ to βb'(1 <= a <= b <= n).
- If q = 1, subtract βkβ to all integers in range βaβ to βb'(1 <= a <= b <= n).
Note: Initially all the array elements are set to β0β and array indexing is from β1β.
Input : n = 5 commands[] = {{0 1 3 2}, {1 3 5 3}, {0 2 5 1}} Output : 0 2 -1 -1 -3 Explanation First command: Add 2 from index 1 to 3 >= 2 2 2 0 0 Second command: Subtract 3 from index 3 to 5 >= 2 2 -1 -3 -3 Third command: Add 1 from index 2 to 5 >= 2 3 0 -2 -2
Simple approach is to execute every command by iterating from left index(l) up-to the right index(r) and update every index according to given command. Time complexity of this approach is O(n*m)
Better approach is to use Fenwick tree(BIT) or segment tree. But it will only optimize upto log(n) time i.e., overall complexity would become O(m*log(n))
Efficient approach is to use simple mathematics. Since all commands can be handled as offline so we can store all updates in our temporary array and then execute it at the last.
- For command β0β, add β+kβ and β-kβ in lth and (r+1)th index elements respectively.
- For command β1β, add β-kβ and β+kβ in the lth and (r+1)th index elements respectively.
After that sum up all the elements for every index βiβ starting from 1st index i.e., ai will contain the sum of all elements from 1 to ith index. This can easily be achieved with the help of dynamic programming.
Implementation:
C++
Java
Python3
C#
Javascript
<script> // javascript program to find modified array // after executing m commands/queries // Update function for every command function updateQuery(arr , n , q , l , r , k) { // If q == 0, add 'k' and '-k' // to 'l-1' and 'r' index if (q == 0) { arr[l - 1] += k; arr[r] += -k; } // If q == 1, add '-k' and 'k' // to 'l-1' and 'r' index else { arr[l - 1] += -k; arr[r] += k; } return ; } // Function to generate the final // array after executing all // commands function generateArray(arr, n) { // Generate final array with the // help of DP concept for (i = 1; i < n; ++i) arr[i] += arr[i - 1]; } // Driver code var n = 5; var arr = Array(n + 1).fill(0); var q = 0, l = 1, r = 3, k = 2; updateQuery(arr, n, q, l, r, k); q = 1; l = 3; r = 5; k = 3; updateQuery(arr, n, q, l, r, k); q = 0; l = 2; r = 5; k = 1; updateQuery(arr, n, q, l, r, k); // Generate final array generateArray(arr, n); // Printing the final modified array for (i = 0; i < n; i++) document.write(arr[i] + " " ); // This code is contributed by aashish1995 </script> |
2 3 0 -2 -2
Time complexity: O(Max(m,n))
Auxiliary space: O(n)