<p>Use a segment tree — a recursive partition of the range $[1,n]$ into smaller ranges. Each interval $[a,b]$ of your update operations can be partitioned into $O(\log n)$ of the ranges in this recursive partition. For each range $[x,y]$ store:</p>

<ul>
<li>The number $c(x,y)$ of intervals $[a,b]$ that have been increased and not decreased such that $[x,y]$ is one of the ranges into which $[a,b]$ is partitioned</li>
<li>The number $u(x,y)$ of cells that are not covered by partitioned subsets of intervals that are at $[x,y]$ or lower in the recursion</li>
</ul>

<p>Then if $[x,y]$ is recursively split into $[x,z]$ and $[z+1,w]$ we have
$$u(x,y)=\begin{cases}
0&amp;\text{if }c(x,y)&gt;0\\
u(x,z)+u(z+1,y)&amp;\text{otherwise}
\end{cases}$$
so we can update each $u(x,y)$ value in constant time when the other data for a range changes. Each support query can be answered by looking at $u(1,n)$.</p>

<p>To perform an increase$(a,b)$ operation, partition $[a,b]$ into $O(\log n)$ ranges, increment $c(x,y)$ for each of these ranges, and use the formula above to recalculate $u(x,y)$ for each of these ranges and each of their ancestors. The decrease operation is the same with a decrement instead of an increment.</p>

CC BY-SA 3.0
2015-05-08T13:52:42.220Z
I don't think I understand your second bullet. In the subtree with rot labeled $[x,y]$, which cells are not covered by partitioned subsets of intervals at $[x,y]$? Isn't the whole range $[x,y]$ covered, so $u(x,y) = 0$?
jbapple
CC BY-SA 3.0
2015-05-08T15:44:16.867Z
It depends on which increase operations you have made. Initially all of them are uncovered, but when you increase a small interval within $[x,y]$ (or any interval that starts or ends within $[x,y]$, or that includes $[x,y]$ in its partition) it decreases.
David Eppstein
CC BY-SA 3.0
2015-05-08T23:01:06.577Z
Could you give an example?
jbapple
CC BY-SA 3.0
2015-05-08T23:34:44.280Z
Suppose your interval is the numbers [1,8]. It is recursively divided into [1,4], [4,8], then [1,2], [3,4], [5,6], and [7,8], then all one-element ranges. Initially, everything is uncovered, all c[x,y]=0, and each range has u=its length. But then, suppose you perform an increase[2,6] operation. The O(log n) maximal ranges into which [2,6] can be decomposed are [2,2], [3,4], and [5,6], so we set c[x,y] for those three ranges to 1. According to the formula in my answer, this causes u[x,y] for these three ranges to also become 0. u[1,2] becomes 1, u[1,4] also becomes 1, u[5,8]=2, and u[1,8]=1+2=3
David Eppstein
CC BY-SA 3.0
2015-05-07T20:15:21.007Z
2015-05-07T20:15:21.007Z
David Eppstein
<p><a href="https://cs.stackexchange.com/questions/14228/how-to-query-and-update-ranges-of-arrays/16761#16761">You can support $\text{increase}$ and $\text{decrease}$ in $O(\sqrt{n}\log n)$ and $\text{support}$ in $O(1)$ time.</a> The key idea is to break up the table into groups of size $\Theta(\sqrt{n})$. Then each modifying operation ($\text{increase}$ or $\text{decrease}$) operates on at most $O(\sqrt{n})$ groups, and only the ones near the end of its range ($a$ and $b$, in your formulation) take $\omega(\log n)$ time.</p>

CC BY-SA 3.0
2015-04-07T16:57:30.243Z
Why not take this approach to the limit. Instead of bucketing into $O(\sqrt{n})$ buckets, we can instead form a tree similar to this:

       1
      / \
     2   3
    / \ / \
   4  5 6  7

Of which, by updating, you take $O(\log{n})$ for all operations.
S. Pek
CC BY-SA 3.0
2015-04-07T15:54:50.320Z
2015-04-07T15:54:50.320Z
2017-04-13T12:48:30.830Z
jbapple
<p>I am looking for a data structure that would maintain an integer table $t$ of size $n$, and allowing the following operations in time $O(\log n)$.</p>

<ul>
<li>$\text{increase}(a,b)$, which increases $t[a],t[a+1],\ldots,t[b]$.</li>
<li>$\text{decrease}(a,b)$, which decreases $t[a],t[a+1],\ldots,t[b]$.</li>
<li>$\text{support}()$, which returns the number of indices $i$ such that $t[i]\neq 0$.</li>
</ul>

<p>You have the promise that every call to decrease can be matched to a previous call to increase with the same parameters $a,b$. The application I have in mind is a sweepline algorithm to compute in time $O(n\log n)$ the area of the union of n given rectilinear rectangles. </p>

<p>A quad-tree would have size $\Theta(n^2)$, so it is not a solution. Fenwick or Interval trees have the right flavor, but I don't see how to extend them to support the operations above.</p>

CC BY-SA 3.0
2013-04-12T08:48:45.227Z
Fenwick trees would not use the promise that "every call to decrease can be matched to a previous call to increase with the same parameters a,b", so there might be a simpler solution using that promise (but it escapes me for now).
J.y B.y
CC BY-SA 3.0
2013-04-12T17:46:09.347Z
Since the number of input you can have is at most $n^2$(you can detect repeats and not insert into the data structure), we still get $O(\log n)$ performance using the common measure tree data structure. See http://www.cosy.sbg.ac.at/~ksafdar/data/courses/SeminarADS/ADS_presentation_1.pdf slide 47-52.
Chao Xu
CC BY-SA 3.0
2013-04-12T21:38:34.887Z
Jérémie and Chao Xu. Thank for your comments.  I understand now how the Interval Tree can be used to maintain the total length of the union of a changing set of intervals.  This is in fact a very cute datastructure.
Christoph Dürr
CC BY-SA 3.0
2013-04-15T07:22:38.350Z
For the general data structure problem, searching in $\log(n^2)\in O(\log(n))$ time requires space $O(p)\subset O(n^2)$ where $p$ is the size of the list of active pairs of coordinates.  But indeed for the sweepline algorithm $p\in O(n)$ so the space stays linear. The problem is still open for a data structure with better space than $O(p)$, when $p\in\omega(n)$.
J.y B.y
CC BY-SA 3.0
2013-04-15T07:25:54.227Z
@ChristophDürr Thinking about it: would not the quad tree have space within $O(n)$ too on your sweepline algorithm, because of the $n$ rectangles? (Then you might want to update your statement in the question.)
J.y B.y
CC BY-SA 3.0
2013-04-15T12:17:12.217Z
Here is a nice link where you can test your implementations against other solutions to the same problem: http://www.spoj.com/OI/problems/NKMARS/
Erel Segal-Halevi
CC BY-SA 3.0
2013-04-16T11:35:23.463Z
@ErelSegalHalevi: Indeed, nice example, Thanks!!!
J.y B.y
CC BY-SA 3.0
2013-04-25T09:34:03.193Z
@ChristophDürr: is there no known algorithm to compute in time O(nlogn) the area of the union of n given rectilinear rectangles in 2 dimensions?
J.y B.y
CC BY-SA 3.0
2015-05-07T20:16:15.330Z
Re computing the area of the union: yes, it has been known how to solve this in $O(n\log n)$ time since the 1970s. See https://en.wikipedia.org/wiki/Klee%27s_measure_problem
David Eppstein
<ds.data-structures><cg.comp-geom>
Data structure for updates on intervals and querying number of zeros
Christoph Dürr
# Data structure for updates on intervals and querying number of zeros

(Asked by: username_0 on 2013-04-11)

I am looking for a data structure that would maintain an integer table $t$ of size $n$, and allowing the following operations in time $O(\log n)$.

* $\text{increase}(a,b)$, which increases $t[a],t[a+1],\ldots,t[b]$.
* $\text{decrease}(a,b)$, which decreases $t[a],t[a+1],\ldots,t[b]$.
* $\text{support}()$, which returns the number of indices $i$ such that $t[i]\neq 0$.

You have the promise that every call to decrease can be matched to a previous call to increase with the same parameters $a,b$. The application I have in mind is a sweepline algorithm to compute in time $O(n\log n)$ the area of the union of n given rectilinear rectangles.

A quad-tree would have size $\Theta(n^2)$, so it is not a solution. Fenwick or Interval trees have the right flavor, but I don't see how to extend them to support the operations above.

**Tags:** ds.data-structures, cg.comp-geom

> **Comments:**
> **username_1**: Fenwick trees would not use the promise that "every call to decrease can be matched to a previous call to increase with the same parameters a,b", so there might be a simpler solution using that promise (but it escapes me for now).  
> **username_2**: Since the number of input you can have is at most $n^2$(you can detect repeats and not insert into the data structure), we still get $O(\log n)$ performance using the common measure tree data structure. See http://www.cosy.sbg.ac.at/~ksafdar/data/courses/SeminarADS/ADS_presentation_1.pdf slide 47-52.  
> **username_0**: Jérémie and username_2. Thank for your comments.  I understand now how the Interval Tree can be used to maintain the total length of the union of a changing set of intervals.  This is in fact a very cute datastructure.  
> **username_1**: For the general data structure problem, searching in $\log(n^2)\in O(\log(n))$ time requires space $O(p)\subset O(n^2)$ where $p$ is the size of the list of active pairs of coordinates.  But indeed for the sweepline algorithm $p\in O(n)$ so the space stays linear. The problem is still open for a data structure with better space than $O(p)$, when $p\in\omega(n)$.  
> **username_1**: @ChristophDürr Thinking about it: would not the quad tree have space within $O(n)$ too on your sweepline algorithm, because of the $n$ rectangles? (Then you might want to update your statement in the question.)  
> **username_3**: Here is a nice link where you can test your implementations against other solutions to the same problem: http://www.spoj.com/OI/problems/NKMARS/  
> **username_1**: @ErelSegalHalevi: Indeed, nice example, Thanks!!!  
> **username_1**: @ChristophDürr: is there no known algorithm to compute in time O(nlogn) the area of the union of n given rectilinear rectangles in 2 dimensions?  
> **username_4**: Re computing the area of the union: yes, it has been known how to solve this in $O(n\log n)$ time since the 1970s. See https://en.wikipedia.org/wiki/Klee%27s_measure_problem  

---

## 2 answers

### Answer by username_4 on 2015-05-07. Score: 3

Use a segment tree — a recursive partition of the range $[1,n]$ into smaller ranges. Each interval $[a,b]$ of your update operations can be partitioned into $O(\log n)$ of the ranges in this recursive partition. For each range $[x,y]$ store:

* The number $c(x,y)$ of intervals $[a,b]$ that have been increased and not decreased such that $[x,y]$ is one of the ranges into which $[a,b]$ is partitioned
* The number $u(x,y)$ of cells that are not covered by partitioned subsets of intervals that are at $[x,y]$ or lower in the recursion

Then if $[x,y]$ is recursively split into $[x,z]$ and $[z+1,w]$ we have
$$u(x,y)=\begin{cases}
0&\text{if }c(x,y)>0\\
u(x,z)+u(z+1,y)&\text{otherwise}
\end{cases}$$
so we can update each $u(x,y)$ value in constant time when the other data for a range changes. Each support query can be answered by looking at $u(1,n)$.

To perform an increase$(a,b)$ operation, partition $[a,b]$ into $O(\log n)$ ranges, increment $c(x,y)$ for each of these ranges, and use the formula above to recalculate $u(x,y)$ for each of these ranges and each of their ancestors. The decrease operation is the same with a decrement instead of an increment.

> **Comments:**
> **username_5**: I don't think I understand your second bullet. In the subtree with rot labeled $[x,y]$, which cells are not covered by partitioned subsets of intervals at $[x,y]$? Isn't the whole range $[x,y]$ covered, so $u(x,y) = 0$?  
> **username_4**: It depends on which increase operations you have made. Initially all of them are uncovered, but when you increase a small interval within $[x,y]$ (or any interval that starts or ends within $[x,y]$, or that includes $[x,y]$ in its partition) it decreases.  
> **username_5**: Could you give an example?  
> **username_4**: Suppose your interval is the numbers [1,8]. It is recursively divided into [1,4], [4,8], then [1,2], [3,4], [5,6], and [7,8], then all one-element ranges. Initially, everything is uncovered, all c[x,y]=0, and each range has u=its length. But then, suppose you perform an increase[2,6] operation. The O(log n) maximal ranges into which [2,6] can be decomposed are [2,2], [3,4], and [5,6], so we set c[x,y] for those three ranges to 1. According to the formula in my answer, this causes u[x,y] for these three ranges to also become 0. u[1,2] becomes 1, u[1,4] also becomes 1, u[5,8]=2, and u[1,8]=1+2=3  

---

### Answer by username_5 on 2015-04-07. Score: 0

[You can support $\text{increase}$ and $\text{decrease}$ in $O(\sqrt{n}\log n)$ and $\text{support}$ in $O(1)$ time.](https://cs.stackexchange.com/questions/14228/how-to-query-and-update-ranges-of-arrays/16761#16761) The key idea is to break up the table into groups of size $\Theta(\sqrt{n})$. Then each modifying operation ($\text{increase}$ or $\text{decrease}$) operates on at most $O(\sqrt{n})$ groups, and only the ones near the end of its range ($a$ and $b$, in your formulation) take $\omega(\log n)$ time.

> **Comments:**
> **username_6**: Why not take this approach to the limit. Instead of bucketing into $O(\sqrt{n})$ buckets, we can instead form a tree similar to this:         1       / \      2   3     / \ / \    4  5 6  7  Of which, by updating, you take $O(\log{n})$ for all operations.  

---

