2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you say anything about in what context you ran across this problem? $\endgroup$ – D.W. Sep 9 '13 at 2:04
  • $\begingroup$ Reposted by same questioner 3 days later as cs.stackexchange.com/questions/14228/… $\endgroup$ – jbapple Nov 7 '13 at 3:22
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.