I want to add to a rectangular section of two-dimensional space and read it out in points.
<ul>
<li>Alternative representation: given a set of rectangles and a point. We want the sum of the number/cost of rectangles containing points <a href="/en/PAST2N">PAST2N</a>.
</li>
<li><a href="/en/Make%20one%20of%20the%20two%20dimensions%20a%20time%20axis.">Make one of the two dimensions a time axis.</a>
</li>
<li>sort add and read on one axis and time axis on the other
<ul>
<li>Range Add at one point and negative Range Add at another point.</li>
<li><img src="https://gyazo.com/2fd0b0bd0c92f206061c4b4ef25c4fec/thumb/1000" alt="image"></li>
</ul>
</li>
<li>When RangeAdd and Read overlap at the same coordinates
<ul>
<li>If the specification is &quot;inside corners too&quot;:.<ul>
<li>The start RangeAdd must be processed before Read.</li>
<li>End RangeAdd must be processed after Read</li>
</ul>
</li>
<li>Shift the coordinates by 0.5<ul>
<li>Start RangeAdd: x -= 0.5</li>
<li>End RangeAdd: x += 0.5</li>
</ul>
</li>
</ul>
</li>
<li>When the range of x values is large, <a href="/en/coordinate%20compression">coordinate compression</a> is required
<ul>
<li>[RangeAdd is two PointAdd</li>
</ul>
</li>
<li><a href="/en/Rectangular%20query">Rectangular query</a>
</li>
</ul>
<hr>
This page is auto-translated from <a href="https://scrapbox.io/nishio/%E9%95%B7%E6%96%B9%E5%BD%A2%E5%8C%BA%E9%96%93add">/nishio/長方形区間add</a> using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at <a href="https://twitter.com/nishio_en">@nishio_en</a>. I&#39;m very happy to spread my thought to non-Japanese readers.

Rectangular section add