Using the euler tour technique let's say disc[u] = discovery time of u and fin[u] = finishing time of u. You must have noticed that for any vertex u, u contains all vertex in the range from disc[u] to fin[u] in its sub-tree.

Using this property you can build a segment tree which handles two operations.

1. query(u, v): returns the summation of all elements from u to v.

2. update(u, x): add x to the position u.

Now when you have a type 1 query for any vertex u, query(disc[u], fin[u]) is your answer. Because all the vertex from disc[u] to fin[u] lie in the sub-tree of vertex u.

For Type 2 query, just call update(disc[u], x).

1st solution :

observation : you always update a leaf node. And if you had a way to update all ancestors of that node, you would do it this way ....

let's say leaf node is updated with x. 1st immediate parent would get updated by x + (2 ^ 0). 2nd parent would get updated by x + (2 ^ 1). 3rd parent would get updated by x + (2 ^ 2). and so on.

Now, root is always 1. let's say we know level of each node respect to that root where level[1] = 0

So if we had to query root 1 what we would do? We would simply add xi + (2 ^ level[i — 1]) for all i, where i represents each leaf node.

But query can include other nodes also. In that case let's assume we can represent a segment tree with each node which can give us sum of subtree of any node.

Now to update a leaf node we would update that node with xi + (2 ^ level[i — 1]) ... meaning value of node 1 only for that particular leaf node is updated in that leaf node.

And if we query a node ..... we will get summation of all the leaf nodes under the subtree of that node ....... which basically is value of node 1 if we only considered leaf nodes under that subtree.

Now , we might not want value of node 1. In that case, get level of target node and divide sum by 2 ^ level[node] .... and that would be ans for query.

But, how can we construct segment tree for tree which can get me sum of subtree for any node? euler tour .... and one comment described it already.

2nd solution:

Now, what about we update the whole tree? This can be done by hld. But that's not the critical part here. Critical part is updating the segment tree inside it.

I describes segment tree part in my blog. you can read it here.....

https://eltonrawn.quora.com/Segment-Tree-Technique-1?srid=J74Y

With 2nd solution we can update any nodes and not just leaf nodes .... which would not be possible with 1st solution.