Not Frequent
0/10

# Range Queries with Sweep Line

Authors: Benjamin Qi, Andi Qu, Dong Liu

Solving 2D grid problems using 1D range queries.

### Prerequisites

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.

Any help would be appreciated! Just submit a Pull Request on Github.

## 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;
void update(int i, int x) {	for (; i < 2000005; i += i & (-i)) bit[i] += x;}int query(int i) {	int sum = 0;

## Solution - Springboards

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

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

1. Add a pair $(a,b)$.
2. 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==query(0,N-1)}. * Time: O(\log N) * Source: * http://codeforces.com/blog/entry/18051 * KACTL * Verification: SPOJ Fenwick */


## Problems

StatusSourceProblem NameDifficultyTags
HEEasy
Show TagsPURS
PlatNormal
Show TagsPURQ
PlatNormal
CSESHard
Show TagsPURQ
IZhOHard

Relating to LIS:

StatusSourceProblem NameDifficultyTags
Balkan OIHard
Show TagsDP, PURS
COCIHard
Show TagsDP, PURS
PlatVery Hard
Show TagsDP

### 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!