snippetMinor
How to query and update ranges of arrays?
Viewed 0 times
arraysupdatequeryrangeshowand
Problem
I have an array of size $N$ $(N \leq 10^5)$. I need to perform two types of operations on the array.
-
Decrease elements in range $[L,R]$ by $X$.
-
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.
-
Decrease elements in range $[L,R]$ by $X$.
-
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.
Solution
Break the array up into $O(\sqrt{n})$ contiguous groups, each of size $O(\sqrt{n})$. With each group, store:
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
- 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
Context
StackExchange Computer Science Q#14228, answer score: 5
Revisions (0)
No revisions yet.