1.
Problem Statement
2.
Constraints
3.
Approach
4.
Code
5.
Time Complexity
6.
Space Complexity
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

# Queries to Calculate Sum of Squares of ASCII Values of Characters of a Substring with updates

## Problem Statement

Given a string s of size N, handle Q queries of the following types:

1. (0, ind, c) : update the character at index ind with character c.
2. (1, l, r) : calculate the sum of squares of the positions of the character in the substring s[l],s[l + 1].....,s[r - 1],s[r] according to english alphabet,

## Constraints

``````1 <= N <= 10^6
1 <= Q <= 10^6
0 <= L, R, ind <= N - 1
``````
``````Sample Test Cases
Input: codingnijas
4
1 0 2
0 1 c
1 0 2
1 2 4
Output: 250
34
293
Explanation:
Initially, the given string is 'codingnijas'
For query(1, 0, 2) (type - 1, L = 0, R = 2), print the answer for the substring 'cod'.
query(1, 0, 2) =  3 * 3 + 15 * 15 + 4 * 4 = 250
For query(0, 1, c) (type - 0, ind = 1, char = c), replace the character at index 1 with character c.
Now, the string is 'ccdingnijas'
Now, for query(1, 0, 2) (type - 1, L = 0, R = 2), print the answer for the substring 'ccd'.
query(1, 0, 2) =  3 * 3 + 3 * 3 + 4 * 4 = 34
For query(1, 2, 4) (type - 1, L = 2, R = 4), print the answer for the substring 'din'.
query(1, 0, 2) =  4 * 4 + 9 * 9 + 14 * 14 = 293``````

## Approach

We strongly recommend to read the below post first

https://www.codingninjas.com/studio/library/range-minimum-query

This problem can be solved efficiently by using the segment tree data structure. We will store the sum of squares of ranges at each node so that we can answer the query and perform the update in O(logN) time complexity.

Steps To Solve

• Define a vector 'Tree' of size 4 * N to store the segment tree. The ith element in the vector Tree denotes a node whose left child is stored at index 2 * i + 1, and the right child is stored at index 2 * i + 2.
• Define the function 'build(int node, int st, int en, string &str)' to build the segment tree from the given string. nodest and en indicate that the sum of squares of ASCII value of character in the substring s[st], s[st + 1],....,s[en - 1], s[en] is stored at the index node in the vector Tree.
• Define the function 'update(int node, int st, int en, int ind, char c)' to update the character at index ind with character c .
• Define the function 'query(int node, int st, int en, int l, int r)' to calculate sum of squares of ASCII values of character in the substring s[l],s[l+ 1]......s[r-1]s[r].
• Build the segment tree by calling the function 'build(0, 0, N - 1, s)', where s is the input string.
• For the query of type (1, l, r) call the function 'query(0, 0, N - 1, l, r)' to get the answer for substring s[l],s[l + 1],.....,s[r - 1], s[r].
• And for the query of type (0, ind, c), call the function update(0, 0, N - 1, ind, c) to update the index ind with character c

## Code

``````#include <bits/stdc++.h>
using namespace std;
//vector to store segment tree
vector <int> Tree;
//function to build the segment tree from the given string
void build(int node, int st, int en, string &str){
//base case
if(st == en){
/*
store the square of position of character according to english alphabets
'a' - 1
'b' - 2
'c' - 3
.
.
'z' - 26
*/
Tree[node] = (str[st] - 'a' + 1) * (str[st] - 'a' + 1);
return;
}
int mid = (st + en)/2;
//build left and right halfs
build(2 * node + 1, st, mid, str);
build(2 * node + 2, mid + 1, en, str);
Tree[node] = Tree[2 * node + 1] + Tree[2 * node + 2];
}
//update function
void update(int node, int st, int en, int ind, char c){
if(ind < st || ind > en)
return;
if(st == en){
//store the square of position of character according to english alphabets
Tree[node] = (c - 'a' + 1) * (c - 'a' + 1);
return;
}
int mid = (st + en)/2;
//update left child
update(2 * node + 1, st, mid, ind, c);
//update right child
update(2 * node + 2, mid + 1, en, ind, c);
//update the current node
Tree[node] = Tree[2 * node + 1] + Tree[2 * node + 2];
}
int query(int node, int st, int en, int l, int r){
//if the segment of node is outside of the given range
if(en < l || st > r)
return 0;
//if the segment of node is completely inside the given range
if(st >= l && en <= r)
return Tree[node];
int mid = (st + en)/2;
//sum of answer of left half and right half of range [l, r]
return query(2 * node + 1, st, mid, l, r) + query(2 * node + 2, mid + 1, en, l, r);
}

signed main(){
//given string
string str;
cin >> str;
int N = str.size();
Tree = vector <int> (4 * N, 0);
//build the segment tree
build(0, 0, N - 1, str);
int Q;
cin >> Q;
while(Q--){
bool type;
cin >> type;
if(type){
//query
int l, r;
cin >> l >> r;
cout << query(0, 0, N - 1, l, r) << "\n";
}
else{
//update
int ind;
char c;
cin >> ind >> c;
update(0, 0, N - 1, ind, c);
}
}
return 0;
}``````

Input

``````codingnijas
4
1 0 2
0 1 c
1 0 2
1 2 4``````

Output

``````250
34
293``````

Also check out - Substr C++ Also see, Euclid GCD Algorithm

## Time Complexity

The time complexity of the build function is O(N), and the time complexity of update and query functions is O(logN). So if there are Q queries, the total time complexity is O(QlogN + 2N).

## Space Complexity

Here space complexity is O(N) as we are using extra space for constructing the segment tree with (2*N - 1) nodes.

Check out this problem - Two Sum Problem

## FAQs

1. What is a segment tree??
A segment tree is a type of data structure that is used to store information about intervals or array segments. Using it, we can efficiently handle update and range queries. It can be stored using an array.

2. Is a segment tree a binary tree?
In a segment tree, every node except leaf nodes has two children, left and right. Therefore, it is a complete binary tree.

3. Why is the build function's time complexity O(N)?
There are 2 * N - 1 nodes in a segment tree, and while building, we process each node once, so the overall time complexity is O(N)

## Key Takeaways

In this article, we solved a problem using the segment tree data structure. The Segment tree is a very flexible data structure, and we can use it to solve a huge number of problems. Check out this coding ninjas' blog for getting a better hold on it.

Recommended problems -

To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning!

Live masterclass