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:
Q X Y: in this type of query we have to decrement each node of the subtree rooted at $X$ by value $Y$.
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.
-
$\begingroup$ Can you say anything about in what context you ran across this problem? $\endgroup$D.W.– D.W. ♦2013年09月09日 02:04:59 +00:00Commented Sep 9, 2013 at 2:04
-
1$\begingroup$ Reposted by same questioner 3 days later as cs.stackexchange.com/questions/14228/… $\endgroup$jbapple– jbapple2013年11月07日 03:22:36 +00:00Commented Nov 7, 2013 at 3:22
1 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.