Queries to update array elements in a range [ L , R ] to satisfy given conditions | C ++ program to implement the above approach ; Function to print the array ; Function to perform the query in range [ L , R ] such that arr [ i ] += i - L + 1 ; Initialize array ; Traverse the query array ; Stores range in 1 - based index ; Update arr1 [ L ] ; Update arr1 [ R + 1 ] ; Update arr2 [ R + 1 ] ; Calculate prefix sum ; Traverse the array , arr2 [ ] ; Copy arr2 [ ] into arr [ ] ; Driver Code ; Given array ; Size of the array ; Stores count of query ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printArray ( int arr [ ] , int N ) { for ( int i = 0 ; i < N ; i ++ ) { cout << arr [ i ] << " ▁ " ; } } void modifyArray ( int arr [ ] , int N , int Q [ ] [ 2 ] , int cntQuery ) { int arr1 [ N + 1 ] = { 0 } ; int arr2 [ N + 1 ] = { 0 } ; for ( int i = 0 ; i < cntQuery ; i ++ ) { int L = Q [ i ] [ 0 ] + 1 , R = Q [ i ] [ 1 ] + 1 ; arr1 [ L ] ++ ; arr1 [ R + 1 ] -- ; arr2 [ R + 1 ] -= R - L + 1 ; } for ( int i = 1 ; i <= N ; i ++ ) arr1 [ i ] += arr1 [ i - 1 ] ; for ( int i = 1 ; i <= N ; i ++ ) arr2 [ i ] += arr2 [ i - 1 ] + arr1 [ i ] ; for ( int i = 1 ; i <= N ; i ++ ) arr [ i - 1 ] = arr2 [ i ] ; printArray ( arr , N ) ; } int main ( ) { int arr [ ] = { 0 , 0 , 0 , 0 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int Q [ ] [ 2 ] = { { 1 , 3 } , { 0 , 1 } } ; int cntQuery = sizeof ( Q ) / sizeof ( Q [ 0 ] ) ; modifyArray ( arr , N , Q , cntQuery ) ; return 0 ; }