bhargav104's blog

By bhargav104, history, 7 years ago, In English

Why do we always break down a query into prefix query when the problem involves Persistent Segment tree is it not possible to directly query a range [L,R]? For example consider this problem and the editorial — http://www.codechef.com/SNCKEL16/problems/SEGSUMQ

If we sort the vectors by the angle and then insert into the persistent segment tree in that order when we get a query <C,D> we can just query that segment tree in which all the vectors in it have lesser angle.

Am i missing something here? Could use some help. Thanks :)

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bhargav104 (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Who told you that you should always break the queries into prefix queries.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's just something that I've noticed in all the blogs and editorials related to this topic. Couldn't figure out why everyone always does it in the prefix query way.