Range and Update Sum Queries with Factorial | CPP program to calculate sum of factorials in an interval and update with two types of operations ; Modulus ; Maximum size of input array ; Size for factorial array ; structure for queries with members type , leftIndex , rightIndex of the query ; function for updating the value ; function for calculating the required sum between two indexes ; function to return answer to queries ; Precomputing factorials ; Declaring a Set ; inserting indexes of those numbers which are lesser than 40 ; update query of the 1 st type ; find the left index of query in the set using binary search ; if it crosses the right index of query or end of set , then break ; update the value of arr [ i ] to its new value ; if updated value becomes greater than or equal to 40 remove it from the set ; increment the index ; update query of the 2 nd type ; update the value to its new value ; If the value is less than 40 , insert it into set , otherwise remove it ; sum query of the 3 rd type ; Driver Code to test above functions ; input array using 1 - based indexing ; declaring array of structure of type queries ; answer the Queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MOD = 1e9 ; const int MAX = 100 ; const int SZ = 40 ; int BIT [ MAX + 1 ] , fact [ SZ + 1 ] ; struct queries { int type , l , r ; } ; void update ( int x , int val , int n ) { for ( x ; x <= n ; x += x & - x ) BIT [ x ] += val ; } int sum ( int x ) { int s = 0 ; for ( x ; x > 0 ; x -= x & - x ) s += BIT [ x ] ; return s ; } void answerQueries ( int arr [ ] , queries que [ ] , int n , int q ) { fact [ 0 ] = 1 ; for ( int i = 1 ; i < 41 ; i ++ ) fact [ i ] = ( fact [ i - 1 ] * i ) % MOD ; set < int > s ; for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] < 40 ) { s . insert ( i ) ; update ( i , fact [ arr [ i ] ] , n ) ; } else update ( i , 0 , n ) ; } for ( int i = 0 ; i < q ; i ++ ) { if ( que [ i ] . type == 1 ) { while ( true ) { auto it = s . lower_bound ( que [ i ] . l ) ; if ( it == s . end ( ) * it > que [ i ] . r ) break ; que [ i ] . l = * it ; int val = arr [ * it ] + 1 ; update ( * it , fact [ val ] - fact [ arr [ * it ] ] , n ) ; arr [ * it ] ++ ; if ( arr [ * it ] >= 40 ) s . erase ( * it ) ; que [ i ] . l ++ ; } } else if ( que [ i ] . type == 2 ) { int idx = que [ i ] . l ; int val = que [ i ] . r ; update ( idx , fact [ val ] - fact [ arr [ idx ] ] , n ) ; arr [ idx ] = val ; if ( val < 40 ) s . insert ( idx ) ; else s . erase ( idx ) ; } else cout << ( sum ( que [ i ] . r ) - sum ( que [ i ] . l - 1 ) ) << endl ; } } int main ( ) { int q = 6 ; int arr [ ] = { 0 , 1 , 2 , 1 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; queries que [ q + 1 ] ; que [ 0 ] . type = 3 , que [ 0 ] . l = 1 , que [ 0 ] . r = 5 ; que [ 1 ] . type = 1 , que [ 1 ] . l = 1 , que [ 1 ] . r = 3 ; que [ 2 ] . type = 2 , que [ 2 ] . l = 2 , que [ 2 ] . r = 4 ; que [ 3 ] . type = 3 , que [ 3 ] . l = 2 , que [ 3 ] . r = 4 ; que [ 4 ] . type = 1 , que [ 4 ] . l = 2 , que [ 4 ] . r = 5 ; que [ 5 ] . type = 3 , que [ 5 ] . l = 1 , que [ 5 ] . r = 5 ; answerQueries ( arr , que , n , q ) ; return 0 ; }