Range Queries on a path in a tree

Question

I came across this question in a contest (which is now over) and I am not able to think of a time-efficient algorithm.

You are given a rooted Tree of N ( <=10^5) nodes . Initially all nodes have value 0.There would be M updates (<=10^5) to the tree which are of the form

Add x y – Add y to node x .

AddUp x y – Add y to x , parent of x , parent of parent of x uptill Root.

After that there will be Q queries ( <=10^5) queries where you will either be asked to give the value of a node or the sum of subtree rooted at that node.

What I did:-

First I tried the naive algorithm that would update each node according to the operation, but obviously it is time taking.

I also thought of using segment trees and Lazy propogation but cannot think of a proper way.

Any help is appreciated , Thanks!

Answer 1

First, construct a graph where the children point to their parents. After that, parse all the updates and store in each node of your tree the sum of Add and AddUp separately. Your node should have the following variables:

sum_add : the sum of all the Add of this node
sum_add_up : the sum of all the AddUp of this node
subtree_sum : the sum of the subtree. Initialize with 0 by now.

Now, transverse your graph using topological order, i.e., you will only process a node if all of its children were already processed, which takes O(N). Let me now define the process function.

process(V) {
    V.sum_add_up = V.sum_add_up + sum(sum_add_up of all V.children)
    V.subtree_sum = V.sum_add + V.sum_add_up + sum(subtree_sum of all V.children)
}

Now you can answer all the queries in O(1). The query for the value of a node V is V.sum_add + V.sum_add_up, and the query for the subtree of V is just V.subtree_sum.