Provided with a string of length N, and Q queries to perform on the string, which includes
Single Index Update
The only solution here is to use a Segment tree to store the pre-processed data in the nodes of our segment tree, where each node will contain the count of vowels in the range [L...R].
For Updates, update the character in the index P with the character V.
Time Complexity :
- Build Tree : O(N)
- Query : O(Log n) per query
Setter’s solution : Can be found here