Loser_'s blog

Segment Tree Problem need help.
By Loser_, history, 5 years ago, In English

In this problem Kuriyama Mirai's Stones I used segment tree for the sum of range of queries.Firstly I created two segment tree (1st for unsorted array)(2nd for sorted array).For every t=1 I used query in unsorted seg_tree and t=2 I used query in sorted seg_tree.Which I know that creating segment tree is in O(n) and query is O(log(n)).But I have TLE for this approach.How can I upgrade this approach? My submission is here.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why segment tree? Prefix sum is enough for the problem.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/blog/entry/12397

→ Reply