Is there any Linear Time algorithm to build Suffix Array? Please provide source code or algorithm link.....
Is there any Linear Time algorithm to build Suffix Array? Please provide source code or algorithm link.....
There is n number of elements & two types of queries. 1st query: update an element by new value 2nd query: how many numbers are greater than k in l to r range.
My approach is by using PST for every 1 to i (1<=i<=n) build a seg tree between 1 to maxValue of elements. Then in the 2nd query, I just calculate how many numbers greater than k in (l-1)'th seg tree & r'th seg tree in o(log N) & give the difference between them.
But in the 1st query, I can't do it by O(log N)......
Here is the problem link: https://www.spoj.com/problems/KQUERY2/en/ My solution: https://ideone.com/mdJeU4
please help it to do it..........