4
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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$ Commented Sep 9, 2013 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$ Commented Sep 9, 2013 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$ Commented Sep 9, 2013 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$ Commented Sep 9, 2013 at 15:17
  • 2
    $\begingroup$ Reposted from 3 days earlier by the same questioner: cs.stackexchange.com/questions/14210/queries-on-tree $\endgroup$ Commented Nov 7, 2013 at 3:23

2 Answers 2

Reset to default
5
$\begingroup$

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.

To 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

Improve this answer
$\endgroup$
0
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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$ Commented Jan 10, 2016 at 14:13
  • $\begingroup$ @TomvanderZanden updates are done in O(lg n) , I will edit my answer, adding how it is done. $\endgroup$ Commented Jan 10, 2016 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.