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.
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.
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.
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).
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 ?
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.
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.
Can you give the problem link?
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.