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

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. node, st 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];
}
//funtion to answer the queries
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 -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String

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!