Range update and point query in segment tree ?

Revision en1, by Ahnaf.Shahriar.Asif, 2018-11-11 16:19:14

Recently I have to solve a problem like : given an array, update n times in range [Li..Ri] and then output the array .I updated them using segment tree and I found the array by querying indexes one by one. It took nlog(n). Can I do it in O(n) ? And additionally, can I find the condition of any index in O(1) ? Thanks in advance.

Tags segment trees, complexity optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Ahnaf.Shahriar.Asif 2018-11-11 16:19:14 386 Initial revision (published)