# Range Queries with Sweep Line

Authors: Benjamin Qi, Andi Qu, Dong Liu

Solving 2D grid problems using 1D range queries.

Focus Problem – try your best to solve this problem before continuing!

Focus Problem – try your best to solve this problem before continuing!

## Tutorial

### This section is not complete.

## Solution - Intersection Points

We can sweep from bottom to top (by the $y$ coordinate); storing two events for vertical segments (one for start and one for end) and one event for horizontal segments.

We can use a Binary Indexed Tree to store the number of **active** vertical
segments for each $x$ coordinate.

Then, every time we encounter the start of a vertical segment, we increment the counter for $x$ in the BIT.

Similarly, we decrement the counter for $x$ every time we see the end of a vertical segment.

When we encounter a horizontal segment, we would query the number of active ranges in $[x_1, x_2]$ where $x_1$ is the lower $x$ coordinate and $x_2$ is the upper $x$ coordinate of the segment.

Our answer would be the sum of all the queries.

C++

#include <bits/stdc++.h>using namespace std;int bit[2000005];void update(int i, int x) {for (; i < 2000005; i += i & (-i))bit[i] += x;}int query(int i) {

## Solution - Springboards

### This section is not complete.

The problem boils down to having a data structure that supports the following operations:

- Add a pair $(a,b)$.
- For any $x$, query the minimum value of $b$ over all pairs satisfying $a\le x$.

The other module describes a simpler way of doing this, though it's probably more straightforward to do coordinate compression and use a min segtree. The latter approach is shown below.

/*** Description: 1D point update, range query where \texttt{comb} is* any associative operation. If $N=2^p$ then \texttt{seg[1]==query(0,N-1)}.* Time: O(\log N)* Source:* http://codeforces.com/blog/entry/18051* KACTL* Verification: SPOJ Fenwick*/

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

HE | Easy | ## Show TagsPURS | |||

Plat | Normal | ## Show TagsPURQ | |||

Plat | Normal | ||||

CSES | Hard | ## Show TagsPURQ | |||

IZhO | Hard |

Relating to LIS:

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Balkan OI | Hard | ## Show TagsDP, PURS | |||

COCI | Hard | ## Show TagsDP, PURS | |||

Plat | Very Hard | ## Show TagsDP |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!