I have an array of size $N$ $(N \leq 10^5)$. I need to perform two types of operations on the array.

  1. Decrease elements in range $[L,R]$ by $X$.

  2. Count the number of negative elements in range $[L,R]$.

There are $10^5$ queries. All I can think about is using a segment tree with lazy propagation, but I believe there would be a better method. The segment tree method will probably time out because in case of alternate update/count queries, this will be close to linear.

  • $\begingroup$ Why don't you just make the queries on your array in time $\Theta(R-L)$? 1) can't be done faster, anyway. What are your runtime goals? What are further restrictions, e.g. space usage and performance of other operations? $\endgroup$ – Raphael Sep 9 '13 at 12:05
  • $\begingroup$ @Raphael there are no restrictions on space. I was sure there would exist an $O(\log n)$ solution for this problem. $\endgroup$ – problemsolverextreme Sep 9 '13 at 14:04
  • $\begingroup$ That's why I'm asking. 2) may be possible in logarithmic-time, but you may have to allow preprocessing and/or higher modification cost. $\endgroup$ – Raphael Sep 9 '13 at 14:23
  • $\begingroup$ @Raphael i am good with a preprocessing cost of the order of O(n Log n) as long as both the queries can be handled in O(Log n). Can you point me to a direction that leads there? $\endgroup$ – problemsolverextreme Sep 9 '13 at 15:17
  • 1
    $\begingroup$ Reposted from 3 days earlier by the same questioner: cs.stackexchange.com/questions/14210/queries-on-tree $\endgroup$ – jbapple Nov 7 '13 at 3:23

Break the array up into $O(\sqrt{n})$ contiguous groups, each of size $O(\sqrt{n})$. With each group, store:

  • A balanced binary search tree (BBST) containing the values of the elements in the array as keys and a pointer to their location in the group as a value.
  • A modifier, $\delta$, indicating some offset that all of the elements have from $0$. For instance, if the elements are stored as $1,2,3$, but actually have the values $-11,-10,-9$, $\delta$ should be $-12$. The idea of $\delta$ is that decreasing the value of all of the elements in a group takes $O(1)$ time.
  • The array elements themselves in array order

To decrease the elements in a range $[R,L]$ where $R$ and $L$ are in the same group, just walk the array and update the BBST for each element. This takes $O(\sqrt{n} \lg n)$ time.

Te decrease the elements in an entire group at once, update $\delta$. This takes $O(1)$ time.

Every range contains $O(\sqrt{n})$ groups at most, and at most two of them are not wholly contained in the range - the end groups. Thus, to decrease a range $[R,L]$ takes $O(\sqrt{n} \lg n)$ total time

To count in a group, find the number of elements in the binary tree less than $-\delta$. This takes $O(\lg n)$ time in a BBST where the nodes are annotated by the sizes of their subtree.

To count in a part of a group, iterate over the array values in that part of the group and count how many are less than $-\delta$. This takes $O(\sqrt{n})$ time.

Again, every range contains $O(\sqrt{n})$ groups at most, and at most two of them are not wholly contained in the range - the end groups. Thus, to count a range $[R,L]$ takes $O(\sqrt{n} \lg n)$ total time


This can be done in O(n lg n) easily with following reduction:
You just want to know how many negatives are there,
Idea : Just look at negative numbers as ones and non-negatives as zero,
Then you have a array of ones and zeros that you want its range sum query, then use Fenwick(BIT) tree or Segment tree to calculate the result.
For updates to be in O(lg n), you have to use normal update routines in Fenwick/Segment tree that works in O(lg n) but you should not insert the real value given to you instead you can replace the given value with one if it is negative and with zero if it is non-negative.

  • $\begingroup$ This means updates would take time proportional to the size of the range updated. I don't think that's what the question author had in mind. $\endgroup$ – Tom van der Zanden Jan 10 '16 at 14:13
  • $\begingroup$ @TomvanderZanden updates are done in O(lg n) , I will edit my answer, adding how it is done. $\endgroup$ – FazeL Jan 10 '16 at 15:10

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.