AVNP5 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Soham Chakrabarti
Tester Arkapravo Ghosh
Editorialist: Soham Chakrabarti

DIFFICULTY :

Easy

PRE-REQUISITES :

Segment tree

PROBLEM EXPLANATION

Provided with a string of length N, and Q queries to perform on the string, which includes

  • Single Index Update

  • Range Queries

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 :

  1. Build Tree : O(N)
  2. Query : O(Log n) per query

Setter’s SOLUTIONS:

Setter’s solution : Can be found here

3 Likes
2

Using Segment tree is the best approach, but it is not the only solution
If anyone doesn’t have the knowledge of Segment tree, he can still solve this problem by using AVL tree, but it will be hectic and time consuming approach.
Refer this solution for AVL tree based approach:
https://www.codechef.com/viewsolution/26113550

1 Like
3

Thanks for the approach and solution.
Yes, It will also work. :heart: