Queries to calculate sum of squares of ASCII values of characters of a substring with updates | Structure of a node of a Segment Tree ; Function to construct the Segment Tree ; If start and end are equal ; Assign squares of positions of the characters ; Stores the mid value of the range [ start , end ] ; Recursive call to left subtree ; Recursive call to right subtree ; Update the current node ; Function to perform the queries of type 2 ; No overlap ; If l <= start and r >= end ; Return the value of treeNode ; Calculate middle of the range [ start , end ] ; Function call to left subtree ; Function call to right subtree ; Return the sum of X and Y ; Function to perform update queries on a Segment Tree ; If start is equal to end and idx is equal to start ; Base Case ; Calculate middle of the range [ start , end ] ; If idx <= mid ; Function call to left subtree ; Otherwise ; Function call to the right subtree ; Update the current node ; Function to perform the given queries ; Stores the segment tree ; Traverse the segment tree ; Assign 0 to each node ; Builds segment tree ; Traverse the query array Q [ ] [ ] ; If query is of type S ; Stores the left boundary ; Stores the right boundary ; Prints the sum of squares of the alphabetic positions of the characters ; Otherwise ; Stores the index of the character to be updated ; Update the segment tree ; Input ; Function call
class treeNode { constructor ( square_sum ) { this . square_sum = square_sum ; } } function buildTree ( s , tree , start , end , treenode ) { if ( start == end ) { tree [ treenode ] . square_sum = Math . pow ( s [ start ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) + 1 , 2 ) ; return ; } let mid = start + Math . floor ( ( end - start ) / 2 ) ; buildTree ( s , tree , start , mid , 2 * treenode ) ; buildTree ( s , tree , mid + 1 , end , 1 + 2 * treenode ) ; tree [ treenode ] . square_sum = tree [ ( 2 * treenode ) ] . square_sum + tree [ ( 2 * treenode ) + 1 ] . square_sum ; } function querySquareSum ( tree , start , end , treenode , l , r ) { if ( ( l > end ) || ( r < start ) ) { return 0 ; } if ( ( l <= start ) && ( r >= end ) ) { return tree [ treenode ] . square_sum ; } let mid = start + Math . floor ( ( end - start ) / 2 ) ; let X = querySquareSum ( tree , start , mid , 2 * treenode , l , r ) ; let Y = + querySquareSum ( tree , mid + 1 , end , 1 + 2 * treenode , l , r ) ; return X + Y ; } function updateTree ( s , tree , start , end , treenode , idx , X ) { if ( ( start == end ) && ( idx == start ) ) { s [ idx ] = X ; tree [ treenode ] . square_sum = Math . pow ( X . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) + 1 , 2 ) ; return ; } let mid = start + Math . floor ( ( end - start ) / 2 ) ; if ( idx <= mid ) { updateTree ( s , tree , start , mid , ( 2 * treenode ) , idx , X ) ; } else { updateTree ( s , tree , mid + 1 , end , ( 2 * treenode ) + 1 , idx , X ) ; } tree [ treenode ] . square_sum = tree [ ( 2 * treenode ) ] . square_sum + tree [ ( 2 * treenode ) + 1 ] . square_sum ; } function PerformQuery ( S , Q ) { let n = S . length ; let tree = new Array ( ( 4 * n ) + 1 ) ; for ( let i = 0 ; i <= ( 4 * n ) ; i = i + 1 ) { tree [ i ] = new treeNode ( 0 ) ; } let s = S . split ( " " ) ; buildTree ( s , tree , 0 , n - 1 , 1 ) ; for ( let i = 0 ; i < Q . length ; i ++ ) { if ( Q [ i ] [ 0 ] == " " ) { let L = parseInt ( Q [ i ] [ 1 ] ) ; let R = parseInt ( Q [ i ] [ 2 ] ) ; document . write ( querySquareSum ( tree , 0 , n - 1 , 1 , L , R ) + " " ) ; } else if ( Q [ i ] [ 0 ] == " " ) { let I = parseInt ( Q [ i ] [ 1 ] ) ; updateTree ( s , tree , 0 , n - 1 , 1 , I , Q [ i ] [ 2 ] [ 0 ] ) ; } } } let S = " " ; let Q = [ [ " " , " " , " " ] , [ " " , " " , " " ] , [ " " , " " , " " ] , [ " " , " " , " " ] , [ " " , " " , " " ] ] PerformQuery ( S , Q ) ;