akash_goel's blog

By akash_goel, 6 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

»
6 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.

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

    Thanks for the comment @Z38. I understand the update part. But how do I query for a single item? I have to get value of all nodes upto the root. That would mean selecting node[x] and some of its predecessors in the ordered array, not all. How would that be done?

  • »
    »
    13 months ago, # ^ |
    Rev. 3   Vote: I like it -7 Vote: I do not like it

    Can we use Fenwick tree for this approach ?

  • »
    »
    5 weeks 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).

»
6 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.

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

    Lets say we have this tree: (2) <- (1) -> (3)

    Now, a dfs traversal with the start and finish might look like this-

    start[1] start[2] finish[2] start[3] finish[3] finish[1].

    And now suppose we only have to find the sum for node (3). That means summing 3+1 = 4. So, if I sum start[3], wont' i get extra values for start[2] and finish[2], unless I do negative updates for finish[x] values. Am I getting this correctly?

»
6 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.

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

    Okay, so this is an HLD question. I don't feel so bad now :)

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

Can you give the problem link?

»
6 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.