PR_0202's blog

How to use segment tree in another tree
By PR_0202, history, 4 years ago, In English

I am confused about how to get sum from a node y to its ancestor x using a segment tree. there is query of 10^5 order consists of update and find sum of the nodes between them.!

  • Vote: I like it
  • +7
  • Vote: I do not like it

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

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

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

Please link the problem.

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

    This problem is a subproblem of another problem

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      You can link that. It’s good to link problems so people know they’re not helping with a problem from an ongoing contest.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    what I did is doing some thing like prefix sum from the root node and for the sum I printed \n tree[y-1].second-tree[x-1].second

    and for update I did this \n

    void update(int y,int z){ tree[y].second+=z; for(int x: tree[y].first){ update(x,z); } } \n I am confused how to do this if O(long) time complexity please help me

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Maintain an array which for every $$$i$$$ will store the sum of all the ancestors(including itself) in $$$array[i]$$$. Now to find the answer for $$$x$$$ and it's anscestor $$$y$$$ it would be equal to $$$array[x]$$$ — $$$array[parentOfY]$$$(similiar as we do in prefix sum from l to r).

Now coming to the update part. When a node value is updated, then what happens? Let $$$x$$$ is updated. Then only the nodes which are in the subtree of $$$x$$$(including itself) are affected, because $$$x$$$ can only be an ancestor of nodes in it's subtree or itself. So when when $$$x$$$ is update do a range update in it's subtree.

Suppose $$$x$$$ was holding value 10($$$a[x]$$$ not $$$array[x]$$$) earlier now it's an update and asks to change it to 5. since all the nodes in it's subtree were holding sum of all of it's ancestor which also includes $$$x$$$ so $$$5 - 10$$$ needs to be added to every nodes in subtree of $$$x$$$ incuding itself. For subtree update you can use preorder traversal.

Fenwick tree would be easier to use here.

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

    But, subtree update if O(n)??

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      See this to flatten a tree into an array. Then for range update we are using fenwick tree or Segment tree so it will be O(log2(N)).

      UPD: I just noticed that the above link answers a more general question and yours is a subset of that one if read it correctly.

      → Reply