Блог пользователя svg_af

Updates on persistent segment tree
Автор svg_af, 8 лет назад, По-английски

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 ??

  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ?

    → Ответить