svg_af's blog

Updates on persistent segment tree
By svg_af, 9 years ago, In English

Hello There I was reading this problem and i noticed that it could be solved with a persistent segment tree which hold multiple of children and every tree is based on the parent's tree

the problem is in this problem we have two types of queries... the second one being update

so i was wondering if updates on a persistent segment tree are possible in log(n) ?

the way i see it updating a certain tree means i have to update all the trees based on it which could lead to linear time...any opinions ??

  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

You need to update only verticles on path from root to leave you need to change(because only this verticles will be changed). So it takes O(logn) time.

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

    so you're saying that changing a node's value i only need to change this node's tree and all trees that are based on this tree don't need changing ?

    → Reply