Perform append, update, delete and range sum queries on the given array
Given an array arr[] of size N and the task is to answer Q queries of the following types:
- 1 X 0: Append X at the back of the array.
- 2 X Y: Set arr[X] = Y.
- 3 X 0: Delete arr[X].
- 4 X Y: Find the sum in the range [X, Y].
Note that after deleting arr[X] in query type 3, all the elements after index X will be shifted left by one position.
Examples:
Input: arr[] = {1, 2, 5, 3, 4}, Q[][] = {
{4, 2, 4},
{3, 3, 0},
{1, 6, 0},
{4, 3, 5}}
Output:
10
13
First Query -> sum(arr[1], arr[2], arr[3])
Second Query -> arr[] = { 1, 2, 3, 4 }
Third Query -> arr[] = { 1, 2, 3, 4, 6 }
Fourth Query -> sum(arr[2], arr[3], arr[4])Input: arr[] = {1, 2, 3, 4, 5}, Q[][] = {
{4, 1, 5},
{3, 3, 0},
{1, 6, 0},
{4, 3, 5},
{2, 4, 10}.
{4, 1, 5}}
Output:
15
15
23
Naive approach: The naive way to solve this problem is to execute the queries directly on the given array which will have a time complexity of O(Q * N).
Efficient approach:
- As there are some data structures like Segment tree or BIT(Fenwick Tree) that provide the point update and range sum in O(logN) per query.
- The post uses a Fenwick Tree to do the same, so it is highly recommended to go through point update in Fenwick Tree.
- But the main problem is performing the delete operation ( type-3 queries ). After performing, there is a need for shifting, which will again lead to O(Q * N) in the worst case.
- A trick can be used that, after deleting an element, just update the value at A[X] = 0 and map the index after X to X + number of elements deleted before X.
- To find the number of elements deleted before X, there will be another Fenwick tree ( as idx in the implementation ) used and keep adding 1 at that index where the delete operation is being performed.
- This means at the time of fetching or getting a particular index, a query can be made to the idx tree and update the index X to X + sum(X, idx).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Size of the array (MAX) const int N = 2e5 + 10; // To store the sum of // the array elements vector< int > bit(N, 0); // To keep track of how many type 3 // queries have been performed before // a particular index vector< int > idx(N, 0); // Function to perform the point // update in Fenwick tree void update( int idx, int val, vector< int >& bitt) { while (idx < N) { bitt[idx] += val; idx += idx & (-idx); } } // Function to return the sum // of the elements A[1...idx] // from BIT int sum( int idx, vector< int >& bitt) { int res = 0; while (idx > 0) { res += bitt[idx]; idx -= idx & (-idx); } return res; } // Function to perform the queries and // return the answer vector vector< int > performQueries(vector< int >& A, vector<vector< int > >& B) { // For 1 bases indexing // insert 0 in the vector A.insert(A.begin(), 0); // Updated size of the vector int n = ( int )A.size(); // Updating the bit tree for ( int i = 1; i < n; ++i) { update(i, A[i], bit); } // Vector to store the answers // of range sum vector< int > ans; // Iterating in the query // vector for ( auto i : B) { int type = i[0]; int x = i[1], v = i[2]; // If the query is of // type 1 if (type == 1) { // Updating the tree // with x in the last update(n, x, bit); // Pushing back the value // in the original vector A.push_back(x); // Incrementing the size // of the vector by 1 n++; } // If the query is of type 2 else if (type == 2) { // Getting the updated index // in case of any query of // type 3 occurred before it int id = x + sum(x, idx); // Making the effect to that // value to 0 by subtracting // same value from the tree update(id, -A[id], bit); // Updating the A[id] to v A[id] = v; // Now update the // bit by v at x update(id, v, bit); } // If the query is of type 3 else if (type == 3) { // Get the current index int id = x + sum(x, idx); // Remove the effect of that // index from the bit tree update(id, -A[id], bit); // Update the idx tree // because one element has // been deleted update(x, 1, idx); // Update the idx val to 0 A[id] = 0; } // If the query is of type 4 else { // Get the updated range int xx = x + sum(x, idx); int vv = v + sum(v, idx); // Push_back the value ans.push_back(sum(vv, bit) - sum(xx - 1, bit)); } } return ans; } // Driver code int main() { vector< int > A = { 1, 2, 5, 3, 4 }; // Queries vector<vector< int > > B = { { 4, 2, 4 }, { 3, 3, 0 }, { 1, 6, 0 }, { 4, 3, 5 }, }; // Get the answer array vector< int > ans = performQueries(A, B); // printing the answer for ( int i : ans) cout << i << "\n" ; return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Size of the array (MAX) static int N = ( int ) 2e5 + 10 ; // To store the sum of // the array elements static int [] bit = new int [N]; // To keep track of how many type 3 // queries have been performed before // a particular index static int [] idx = new int [N]; // Function to perform the point // update in Fenwick tree static void update( int idx, int val, int [] bitt) { while (idx < N) { bitt[idx] += val; idx += idx & (-idx); } } // Function to return the sum // of the elements A[1...idx] // from BIT static int sum( int idx, int [] bitt) { int res = 0 ; while (idx > 0 ) { res += bitt[idx]; idx -= idx & (-idx); } return res; } // Function to perform the queries and // return the answer vector static Vector<Integer> performQueries(Vector<Integer> A, int [][] B) { // For 1 bases indexing // insert 0 in the vector A.insertElementAt( 0 , 0 ); // Updated size of the vector int n = ( int ) A.size(); // Updating the bit tree for ( int i = 1 ; i < n; ++i) { update(i, A.elementAt(i), bit); } // Vector to store the answers // of range sum Vector<Integer> ans = new Vector<>(); // Iterating in the query // vector for ( int [] i : B) { int type = i[ 0 ]; int x = i[ 1 ], v = i[ 2 ]; // If the query is of // type 1 if (type == 1 ) { // Updating the tree // with x in the last update(n, x, bit); // Pushing back the value // in the original vector A.add(x); // Incrementing the size // of the vector by 1 n++; } // If the query is of type 2 else if (type == 2 ) { // Getting the updated index // in case of any query of // type 3 occurred before it int id = x + sum(x, idx); // Making the effect to that // value to 0 by subtracting // same value from the tree update(id, -A.elementAt(id), bit); // Updating the A[id] to v A.set(id, v); // Now update the // bit by v at x update(id, v, bit); } // If the query is of type 3 else if (type == 3 ) { // Get the current index int id = x + sum(x, idx); // Remove the effect of that // index from the bit tree update(id, -A.elementAt(id), bit); // Update the idx tree // because one element has // been deleted update(x, 1 , idx); // Update the idx val to 0 A.set(id, 0 ); } // If the query is of type 4 else { // Get the updated range int xx = x + sum(x, idx); int vv = v + sum(v, idx); // Push_back the value ans.add(sum(vv, bit) - sum(xx - 1 , bit)); } } return ans; } // Driver Code public static void main(String[] args) { Integer[] a = { 1 , 2 , 5 , 3 , 4 }; Vector<Integer> A = new Vector<Integer>(Arrays.asList(a)); // Queries int [][] B = { { 4 , 2 , 4 }, { 3 , 3 , 0 }, { 1 , 6 , 0 }, { 4 , 3 , 5 } }; // Get the answer array Vector<Integer> ans = peformQueries(A, B); // printing the answer for ( int i : ans) System.out.println(i); } } // This code is contributed by // sanjeev2552 |
Python3
# Python implementation of the approach # Size of the array (MAX) N = int ( 2e5 ) + 10 # To store the sum of # the array elements bit = [ 0 ] * N # To keep track of how many type 3 # queries have been performed before # a particular index idx = [ 0 ] * N # Function to perform the point # update in Fenwick tree def update(index: int , val: int , bitt: list ): while index < N: bitt[index] + = val index + = index & - index # Function to return the sum # of the elements A[1...idx] # from BIT def summation(index: int , bitt: list ) - > int : res = 0 while index > 0 : res + = bitt[index] index - = index & - index return res # Function to perform the queries and # return the answer vector def performQueries(A: list , B: list ) - > list : global bit, idx # For 1 bases indexing # insert 0 in the vector A.insert( 0 , 0 ) # Updated size of the vector n = len (A) # Updating the bit tree for i in range ( 1 , n): update(i, A[i], bit) # Vector to store the answers # of range sum ans = [] # Iterating in the query # vector for i in B: type = i[ 0 ] x = i[ 1 ] v = i[ 2 ] # If the query is of # type 1 if type = = 1 : # Updating the tree # with x in the last update(n, x, bit) # Pushing back the value # in the original vector A.append(x) # Incrementing the size # of the vector by 1 n + = 1 # If the query is of type 2 elif type = = 2 : # Getting the updated index # in case of any query of # type 3 occurred before it id = x + summation(x, idx) # Making the effect to that # value to 0 by subtracting # same value from the tree update( id , - A[ id ], bit) # Updating the A[id] to v A[ id ] = v # Now update the # bit by v at x update( id , v, bit) # If the query is of type 3 elif type = = 3 : # Get the current index id = x + summation(x, idx) # Remove the effect of that # index from the bit tree update( id , - A[ id ], bit) # Update the idx tree # because one element has # been deleted update(x, 1 , idx) # Update the idx val to 0 A[ id ] = 0 # If the query is of type 4 else : # Get the updated range xx = x + summation(x, idx) vv = v + summation(v, idx) # Push_back the value ans.append(summation(vv, bit) - summation(xx - 1 , bit)) return ans # Driver Code if __name__ = = "__main__" : A = [ 1 , 2 , 5 , 3 , 4 ] # Queries B = [[ 4 , 2 , 4 ], [ 3 , 3 , 0 ], [ 1 , 6 , 0 ], [ 4 , 3 , 5 ]] # Get the answer array ans = performQueries(A, B) # printing the answer for i in ans: print (i) # This code is contributed by # sanjeev2552 |
Javascript
<script> // Javascript implementation of the approach // Size of the array (MAX) const N = 2e5 + 10; // To store the sum of // the array elements let bit = new Array(N).fill(0); // To keep track of how many type 3 // queries have been performed before // a particular index let idx = new Array(N).fill(0); // Function to perform the point // update in Fenwick tree function update(idx, val, bitt) { while (idx < N) { bitt[idx] += val; idx += idx & (-idx); } } // Function to return the sum // of the elements A[1...idx] // from BIT function sum(idx, bitt) { let res = 0; while (idx > 0) { res += bitt[idx]; idx -= idx & (-idx); } return res; } // Function to perform the queries and // return the answer vector function performQueries(A, B) { // For 1 bases indexing // insert 0 in the vector A.unshift(0); // Updated size of the vector let n = A.length; // Updating the bit tree for (let i = 1; i < n; ++i) { update(i, A[i], bit); } // Vector to store the answers // of range sum let ans = new Array(); // Iterating in the query // vector for (let i of B) { let type = i[0]; let x = i[1], v = i[2]; // If the query is of // type 1 if (type == 1) { // Updating the tree // with x in the last update(n, x, bit); // Pushing back the value // in the original vector A.push(x); // Incrementing the size // of the vector by 1 n++; } // If the query is of type 2 else if (type == 2) { // Getting the updated index // in case of any query of // type 3 occurred before it let id = x + sum(x, idx); // Making the effect to that // value to 0 by subtracting // same value from the tree update(id, -A[id], bit); // Updating the A[id] to v A[id] = v; // Now update the // bit by v at x update(id, v, bit); } // If the query is of type 3 else if (type == 3) { // Get the current index let id = x + sum(x, idx); // Remove the effect of that // index from the bit tree update(id, -A[id], bit); // Update the idx tree // because one element has // been deleted update(x, 1, idx); // Update the idx val to 0 A[id] = 0; } // If the query is of type 4 else { // Get the updated range let xx = x + sum(x, idx); let vv = v + sum(v, idx); // Push the value ans.push(sum(vv, bit) - sum(xx - 1, bit)); } } return ans; } // Driver code let A = [1, 2, 5, 3, 4]; // Queries let B = [ [4, 2, 4], [3, 3, 0], [1, 6, 0], [4, 3, 5], ]; // Get the answer array let ans = peformQueries(A, B); // printing the answer for (let i of ans) document.write(i + "<br>" ); // This code is contributed by gfgking </script> |
C#
// C# implementation of the approach using System; using System.Collections.Generic; using System.Linq; class GFG { // Size of the array (MAX) static int N = ( int ) 2e5 + 10; // To store the sum of // the array elements static int [] bit = new int [N]; // To keep track of how many type 3 // queries have been performed before // a particular index static int [] idx = new int [N]; // Function to perform the point // update in Fenwick tree static void update( int idx, int val, int [] bitt) { while (idx < N) { bitt[idx] += val; idx += idx & (-idx); } } // Function to return the sum // of the elements A[1...idx] // from BIT static int sum( int idx, int [] bitt) { int res = 0; while (idx > 0) { res += bitt[idx]; idx -= idx & (-idx); } return res; } // Function to perform the queries and // return the answer vector static List< int > performQueries(List< int > A, int [][] B) { // For 1 bases indexing // insert 0 in the vector A.Insert(0, 0); // Updated size of the vector int n = A.Count(); // Updating the bit tree for ( int i = 1; i < n; ++i) { update(i, A.ElementAt(i), bit); } // Vector to store the answers // of range sum List< int > ans = new List< int >(); // Iterating in the query // vector foreach ( int [] i in B) { int type = i[0]; int x = i[1], v = i[2]; // If the query is of // type 1 if (type == 1) { // Updating the tree // with x in the last update(n, x, bit); // Pushing back the value // in the original vector A.Add(x); // Incrementing the size // of the vector by 1 n++; } // If the query is of type 2 else if (type == 2) { // Getting the updated index // in case of any query of // type 3 occurred before it int id = x + sum(x, idx); // Making the effect to that // value to 0 by subtracting // same value from the tree update(id, -A.ElementAt(id), bit); // Updating the A[id] to v A[id] = v; // Now update the // bit by v at x update(id, v, bit); } // If the query is of type 3 else if (type == 3) { // Get the current index int id = x + sum(x, idx); // Remove the effect of that // index from the bit tree update(id, -A.ElementAt(id), bit); // Update the idx tree // because one element has // been deleted update(x, 1, idx); // Update the idx val to 0 A[id] = 0; } // If the query is of type 4 else { // Get the updated range int xx = x + sum(x, idx); int vv = v + sum(v, idx); // Push_back the value ans.Add(sum(vv, bit) - sum(xx - 1, bit)); } } return ans; } // Driver code public static void Main( string [] args) { List< int > A = new List< int >( new int [] { 1, 2, 5, 3, 4 }); // Queries int [][] B = new int [][] { new int [] { 4, 2, 4 }, new int [] { 3, 3, 0 }, new int [] { 1, 6, 0 }, new int [] { 4, 3, 5 } }; // Get the answer array List< int > ans = performQueries(A, B); // printing the answer foreach ( int i in ans) Console.WriteLine(i); } } |
10 13
Time Complexity: O(Q * logN + NlogN)
Auxiliary Space: O(N).
Contact Us