Queries on Tree

Question

We have a tree with $N$ nodes. $N \le 10^5.$ Each node has a value $V$ associated with it. Now we have $Q$ $(\le 10^5)$ queries. There are two types of queries:

1. Q X Y: in this type of query we have to decrement each node of the subtree rooted at $X$ by value $Y$.

2. C X: in this type of query we have to count the number of nodes in the subtree rooted at $X$ that are $\le 0$.

Here is my approach: I can perform the update query in $O(N)$ along with some sort of lazy propogation. The count query can be thus performed in constant time.

But I am more than sure that there will be a better approach to handle update queries. Possibly a $O(\log N)$ bound for both updates and counts. Is there a way I could map this tree into a segment tree or a bit.

Any approach would be appreciated.

Answer 1

You can do a bit better, if you augment the data structure with some additional information at each node. You can make each query Q X Y run in $O(1)$ time (just update a single number at the node $X$). Also, you can make each C X query run in $O(D+n(X))$ time, where $n(X)$ is the number of nodes underneath $X$ (follow the path from the root down to $X$ to accumulate the effect of all previous Q-queries on any ancestor of $X$; then recursively explore all of $X$'s descendants, taking into account the effect of all $Q$-queries on descendants of $X$ as you go).

It feels like it ought to be possible to do better, but I don't immediately have a suggestion.