akash_goel's blog

Fastest way to update and query a subtree
By akash_goel, 9 years ago, In English

I recently found this question -

You have a tree of N nodes, and you can do M queries on the tree. The queries are of two types-

1 a x — add a to node x and all its descendents

2 x — find the sum of values of all nodes in the path b/w the root node and the node x (both root and x inclusive).

My brute-force approach — O(N*M)

Made a parent array for parent of each node, and a child vector of sets for children of each node. Also take an upd[n] and val[n] array to keep current pending update and value for each node.

For query 1 (update), just do upd[x] := upd[x] + a

For query 2 (sum from x to root), go backwards from x to root (using parent array), sum all the values along the way, apply val[i] := val[i]+upd[i] (i is b/w root and x) and update upd[y], where y is child of i.

http://ideone.com/IWDHtp

And as expected, it gives TLE for some test cases.

What is a faster approach for this? I am unable to come up with anything that updates and queries in less time.

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

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

Have you heard about Eulerian ordering of the tree nodes?
Do it like this: call a single DFS from the root of the tree, and once a node is visited, simply append it to your list.
We can notice that now every subtree of our tree can be described by a consecutive subsequence of the ordering. This can be used in many problems which involve some subtree stuff.
Coming back to your task, let path[i] be the sum of the values on the path from i to root.
Then performing query1(x, val) will only change path[v] for v in the subtree of x.
You can precalculate the sizes of subtrees for all nodes and create a segment tree, then
all you'll have to do is addOnSegment(1, 1, n, posInOrder[x], posInOrder[x] + sizeOfSubtree[x] — 1, val) (this is just a usual segment tree)
To answer the second query you should simply refer to getElement(1, 1, n, posInOrder[x]).
That's all, hope that helps :)
Feel free to ask any questions.

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

    Consider Tree = [ 1-2, 2-3, 3-4, 2-5] and Node values = [ 1,2,3,4,5 ].

    Acc. to your idea path[i] = [1, 3, 6, 10, 8].

    If we do type 1 query: 1 10 3. Now, new node values = [ 1, 2, 13, 14, 5] and path[i] = [1, 3, 16, 30, 8].

    But if we do acc. to what you suggested, addOnSegment(1,1,5,3,4,10) and then getElement(1,1,5,4) we get answer as 20 but req and is 30.

    Pls correct if i'am wrong.

    I think path[i] for all node y under subtree x will have to add val * (distance x-y).

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

    I get the approach upto precalculating treesizes, but if we update a value of node x then path[v] where v belongs to nodes in subtree of x will be changed by different numbers not a single number.

    consider tree 1->2->3;

    path[] = [1,4,6]

    if i update on 2->4(adding 2 to node 2 and it's subnodes) then new tree and paths are

    tree 1->4->5;

    path[] = [1,5,10];

    so node 2 got increased by 2 but node 3 by in path[] got increased by 4. i can manage if nodes in subtree get increased by specific amount but here values by which nodes are increasing are variable. how to deal with it ?

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

Lets do a dfs on the tree

say we have 2 values

start[node] which denotes the time at which we enter this node during dfs

finish[node] which denotes the time at which we leave this node during dfs

Now for any node say 'X' and another node 'Y' in its subtree , start[X] < start[Y] <= finish[Y] <= finish[X]. So when we are adding a number 'A' to subtree of 'X' , we do a lazy update of adding a number 'A' to all indices from start[X] to finish[X] , we can do this with a segment tree or bit.

Now for a query , we just need to do sum(start[node]) to get the sum from root to this node , this works because for all updates which are done on any ancestor of this node will update the value at start[node] as well.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

If you do an update with value a at a node of depth d1, then every node in the subtree will be affected. Say a node in the subtree has depth d2. Then it will change the value of a query on that node by a(d2 - d1 + 1). Rearranging, we have  - a(d1 + 1) + ad2: one constant term, and one which depends on d2. So, query the constant term and the variable term separately, using HLD.

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

Can you give the problem link?

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

It can be done in O(sqrtM*N*logN) using square-root decomposition and LCA .

We will divide the queries into blocks of sqrtM size.

Maintain an array SUM[] to store the sum from node to root for all nodes. But this array needs to be updated. So, we will update it after every Sqrt(M) queries(blocks) using the update queries that happened in that block.It can be done using a single dfs in O(N) time.

Now to query for a node say x, first we will add to result SUM[x]. This doesn't account for updates happened in the current block of queries till now. So, consider each of those updates separately and check if the update node(say y) is an ancestor of node x.If yes, then add (update value)*(height[x]-height[y]+1) to the answer.

→ Reply