Sweep Line

Quick Revisit
USE WHEN: interval union length, overlap counting, or 2D problem reducible to 1D event processing
INVARIANT: events sorted by x; active set tracks objects currently crossing the sweep line
TIME: O(n log n) | SPACE: O(n)
CLASSIC BUG: wrong tie-breaking in event order — open-before-close vs close-before-open depends on problem
PRACTICE: 08-ladder-mixed

Process geometric and interval problems in $O (n \log n)$ by sweeping an imaginary line across sorted events -- converting a 2D spatial problem into a 1D sequence of updates.

Difficulty: [Intermediate]Prerequisites: Sorting, Segment Tree, Coordinate CompressionCF Rating: 1500-1900

2. Intuition
3. C++ STL Reference
4. Implementation (Contest-Ready)
5. Operations Reference
6. Problem Patterns & Tricks
7. Contest Cheat Sheet
8. Gotchas & Debugging
9. Self-Test
10. Practice Problems
11. Further Reading

Intuition

You have three intervals on a number line: $[1, 5]$ , $[3, 8]$ , $[6, 10]$ . Find the total length covered by their union.

  0  1  2  3  4  5  6  7  8  9  10
  .  [--------]                .       [1,5]  length 4
  .  .  .  [----------]       .       [3,8]  length 5
  .  .  .  .  .  .  [--------]       [6,10]  length 4

Your first instinct: check every pair of intervals, compute their overlap, use inclusion-exclusion.

  |A| + |B| + |C| - |A^B| - |A^C| - |B^C| + |A^B^C|
  = 4 + 5 + 4 - 2 - 0 - 2 + 0 = 9

That works for 3 intervals -- 3 pairwise intersections, 1 triple. But with $n$ intervals, you have $(\binom{n}{2})$ pairs, $(\binom{n}{3})$ triples, all the way up to $(\binom{n}{n})$ -- the formula has $2^{n} - 1$ terms. Even for $n = 30$ , that is over a billion terms. Completely intractable.

What if you try a simpler approach -- for each integer point, check if it falls inside any interval? That is $O (n \cdot L)$ where $L$ is the range of coordinates. With coordinates up to $10^{9}$ , this is also hopeless.

We are recomputing overlaps between every possible combination. There has to be a better way.

Instead of checking all pairs of intervals, sweep an imaginary line from left to right, processing events (interval opens and closes) in sorted order -- at each event, you know exactly how many intervals are active.

Think of a librarian doing inventory of borrowed books. Instead of comparing every pair of checkout dates to find overlaps, she walks through her calendar day by day. Each day she sees who checked out and who returned. At any moment, she knows exactly which books are out -- the "active set."

  Calendar:   1     3     5  6     8     10
  Events:    +A    +B    -A +C    -B    -C
  Active:    {A}  {A,B} {B} {B,C} {C}   {}

The analogy fits well: events are sorted, and the active state updates incrementally. It breaks when events happen at the same coordinate -- the librarian must carefully process all opens before closes at the same time (or vice versa, depending on the problem). Tie-breaking order matters and is a common source of bugs.

Visual Walkthrough

Same three intervals -- now solved with a sweep line.

Step 1: Extract events

Each interval $[l, r]$ produces two events: an "open" at $l$ and a "close" at $r$ .

  Interval [1,5]  --> (+1 at x=1),  (-1 at x=5)
  Interval [3,8]  --> (+1 at x=3),  (-1 at x=8)
  Interval [6,10] --> (+1 at x=6),  (-1 at x=10)

Step 2: Sort events by x-coordinate

  x=1  +1     (open)
  x=3  +1     (open)
  x=5  -1     (close)
  x=6  +1     (open)
  x=8  -1     (close)
  x=10 -1     (close)

Step 3: Sweep left to right, track active count

  x:      1     3     5     6     8     10
  event: +1    +1    -1    +1    -1    -1
  active: 1     2     1     2     1     0
          |     |     |     |     |     |
  0  1  2  3  4  5  6  7  8  9  10
  .  |-----|-----|-----|-----|-----|
     ^     ^     ^     ^     ^     ^
     x=1   x=3   x=5   x=6   x=8   x=10

  Between events, active > 0 means covered:
    [1,3): active=1, length = 3-1 = 2    covered
    [3,5): active=2, length = 5-3 = 2    covered
    [5,6): active=1, length = 6-5 = 1    covered
    [6,8): active=2, length = 8-6 = 2    covered
    [8,10): active=1, length = 10-8 = 2  covered

  Total covered = 2 + 2 + 1 + 2 + 2 = 9

Operation count comparison:

  Inclusion-exclusion:  2^n - 1 terms --> exponential
  Point-by-point:       O(n * L)      --> too slow for large L
  Sweep line:           O(n log n)    --> sort + linear scan

The Invariant

+------------------------------------------------------------------+
| INVARIANT: At sweep position x, the counter 'active' equals the  |
| number of intervals [l,r] satisfying l <= x < r.                 |
|                                                                   |
| Maintained by: incrementing active at each open event (+1) and    |
| decrementing at each close event (-1), processed in sorted order. |
+------------------------------------------------------------------+

Why it holds: Before the first event, active $= 0$ and no interval covers any point to the left. Each open event at $x = l$ adds exactly the interval that starts at $l$ . Each close event at $x = r$ removes exactly the interval that ends at $r$ . Because events are sorted, by the time we process event at $x$ , all intervals opening before $x$ have been added and all intervals closing before $x$ have been removed. By induction, active is correct at every event point.

Look at Step 3 above: after processing $x = 3$ (open), active $= 2$ , and indeed both $[1, 5]$ and $[3, 8]$ cover position 3. After processing $x = 5$ (close), active $= 1$ , and only $[3, 8]$ covers position 5.

Between consecutive events, no interval opens or closes, so active remains constant. This is why we can compute the contribution of a segment as $(next_x - curr_x)$ times (1 if active $> 0$ , else 0).

When to Reach for This

  Sweep line moving left to right through segment events:

       |                          |
       |  *---seg1---*            |
       |     *---seg2---*         |
       |         *---seg3-----*   |
       |              *--seg4--*  |
  -----+----+----+----+----+-----+---> x
       e1   e2   e3   e4   e5
      (start)(start)(start (start)(end
                     /end)        /end)

  Events sorted by x-coordinate.
  Active set = {segments currently crossing the sweep line}

Trigger phrases -- if you see these in a problem statement, think sweep line:

"Total length covered by the union of $n$ intervals" -- classic 1D sweep, the bread and butter.
"Maximum number of overlapping intervals at any point" -- sweep and track max of active counter.
"Area of the union of $n$ rectangles" -- 2D sweep: sweep one axis, use a segment tree on the other.
"Perimeter of the union of rectangles" -- similar to area but count boundary transitions.
"Closest pair of points" -- sweep with a balanced BST of active points sorted by $y$ .
"Count intersections among line segments" -- sweep with ordered structure for active segments.

Counter-examples -- problems that look like sweep line but need a different tool:

"Merge overlapping intervals into non-overlapping ones." This is just sorting by left endpoint and greedily merging -- no sweep line data structure needed. A simple $O (n \log n)$ sort + one pass suffices. See: 10-greedy.md.
"Point-in-rectangle queries for $Q$ queries." If the rectangles are static and queries are online, a persistent segment tree or 2D prefix sum is usually better. Sweep line works for offline queries, but for online queries see: 15-segment-tree.md.
"Interval scheduling (maximum non-overlapping intervals)." This is a greedy problem (sort by right endpoint, pick greedily). The sweep idea does not help because you need to make selection decisions, not just count overlaps.

What the Code Won't Teach You

Recognizing sweep line opportunities. The key signal: a problem involves intervals or rectangles, and you want some property of their union or intersection. Or: you have $n$ elements with two attributes and you want to count pairs where one dominates the other in both attributes. The template code will not teach you to see this -- only practice with diverse problem statements will.

The event design is the creative step. The code templates show pre-built event structures, but in a contest you must decide: what are the events? What information does each carry? For "area of union of rectangles," the events are vertical edges; for "count inversions," the events are elements processed in a specific order. This design step is invisible in finished code.

Sweep line as a paradigm, not a trick. The pattern -- reduce a 2D problem to a sequence of 1D problems by sweeping one dimension -- extends beyond geometry. It is the idea behind many offline algorithms (process queries sorted by right endpoint, maintain a BIT for the left). Seeing sweep line as a paradigm expands where you can apply it.

Two distinct sweep regimes -- this file is the first.

1D event sweeps (this file). Events are points on a single axis with a $\pm 1$ "type". The state is a counter or a histogram. No geometric ordering of the active objects is required -- you only need to know how many are active. Examples: interval union length, maximum overlap, rectangle area union with a segment tree on the orthogonal axis.
Geometry sweeps with an ordered active set. The active objects (line segments, points) need to be kept in a balanced BST sorted by some key (y-coordinate, angular order). Inserts, deletes, and neighbor queries on the active set are the inner-loop operations. Examples: Bentley-Ottmann line-segment intersection, closest pair with an active set indexed by y. These belong in Chapter 8 -- Geometry Sweep Line, which covers them with the geometric primitives they depend on.

The two regimes share the outer loop ("sort events, process in order") but differ in what the active state looks like. If your sweep needs set::lower_bound on the active set, it is the geometry flavor.

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
`sort(first, last)`	`<algorithm>`	Sort events by coordinate. Core of every sweep.	$O (n \log n)$
`sort(first, last, cmp)`	`<algorithm>`	Sort with custom comparator for tie-breaking.	$O (n \log n)$
`multiset<T>`	`<set>`	Active set for closest-pair sweep (ordered by $y$ ).	$O (\log n)$ per op
`set<T>`	`<set>`	Active set when duplicates not needed.	$O (\log n)$ per op
`map<int,int>`	`<map>`	Coordinate-to-count mapping for compressed sweep.	$O (\log n)$ per op
`lower_bound(first, last, val)`	`<algorithm>`	Find position in sorted coordinate array for compression.	$O (\log n)$
`unique(first, last)`	`<algorithm>`	Remove duplicate coordinates after sorting (compression).	$O (n)$
`priority_queue<T>`	`<queue>`	Alternative to multiset for closest-pair or scheduling sweeps.	$O (\log n)$ push/pop

Implementation (Contest-Ready)

Event Tie-Breaking at the Same Coordinate

When two events share the same x-coordinate, the processing order matters. The "right" order is problem-dependent and is the #1 source of bugs in sweep-line code. The table below captures the common cases:

Problem	Event order at same x	Why
Closed intervals $[l, r]$ , maximum overlap	open before close	$[2, 5]$ and $[5, 8]$ both cover the point $x = 5$ ; closing $[2, 5]$ first under-counts
Half-open intervals $[l, r)$ , union length	close before open	$[2, 5)$ and $[5, 8)$ are disjoint at $x = 5$ ; opening $[5, 8)$ first inflates active count
Closed intervals $[l, r]$ , union length	either order works	both give the same total length when the gap to the next event is computed correctly
Counting integer points covered (closed)	open before close, then read active after opens	the point $x$ is covered iff at least one interval has $l \leq x \leq r$
Rectangle area union (sweep on x, segtree on y)	open before close	a rectangle starting at $x$ contributes from $x$ onward; closing first creates a sliver gap
Maximum simultaneous overlaps	open before close	the moment of contact at the shared endpoint is when the maximum is achieved

Implementation: Sort events as {x, type} where type is 0 for start, 1 for end -- the default pair<int,int> comparison places starts (type=0) before ends (type=1) at the same x. Reverse the types (start=1, end=0) if you need end-before-start, or use a custom comparator. When in doubt, hand-trace two adjacent intervals like $[1, 3]$ and $[3, 5]$ on your specific problem.

Version 1: Minimal Contest Template

1D interval union length:

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> events; // (x, type): +1 open, -1 close
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        events.push_back({l, +1});
        events.push_back({r, -1});
    }
    sort(events.begin(), events.end());

    long long total = 0;
    int active = 0, prev_x = 0;
    for (auto [x, type] : events) {
        if (active > 0) total += x - prev_x;
        active += type;
        prev_x = x;
    }
    cout << total << "\n";
}

Maximum overlap count:

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> events;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        events.push_back({l, +1});
        events.push_back({r, -1});
    }
    // Tie-break: opens (+1) before closes (-1) at same x
    sort(events.begin(), events.end(), [](auto& a, auto& b) {
        return a.first < b.first || (a.first == b.first && a.second > b.second);
    });

    int active = 0, best = 0;
    for (auto [x, type] : events) {
        active += type;
        best = max(best, active);
    }
    cout << best << "\n";
}

2D rectangle area union (sweep + segment tree with lazy propagation):

cpp

#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    int n;
    vector<int> cnt;    // cover count from rectangle events
    vector<long long> len; // total covered length in this node's range
    vector<int> coords; // y-coordinates (compressed)

    SegTree() = default;
    SegTree(vector<int>& ys) : coords(ys) {
        n = (int)ys.size() - 1;
        cnt.assign(4 * n, 0);
        len.assign(4 * n, 0);
    }

    void push_up(int v, int lo, int hi) {
        if (cnt[v] > 0)
            len[v] = coords[hi + 1] - coords[lo];
        else if (lo == hi)
            len[v] = 0;
        else
            len[v] = len[2*v] + len[2*v+1];
    }

    void update(int v, int lo, int hi, int ql, int qr, int val) {
        if (ql > hi || qr < lo) return;
        if (ql <= lo && hi <= qr) {
            cnt[v] += val;
            push_up(v, lo, hi);
            return;
        }
        int mid = (lo + hi) / 2;
        update(2*v, lo, mid, ql, qr, val);
        update(2*v+1, mid+1, hi, ql, qr, val);
        push_up(v, lo, hi);
    }

    void update(int ql, int qr, int val) {
        if (ql > qr) return;
        update(1, 0, n - 1, ql, qr, val);
    }

    long long query() { return len[1]; }
};

int main() {
    int n;
    cin >> n;

    // Each rectangle: (x1, y1, x2, y2), covering [x1,x2] x [y1,y2]
    struct Event { int x, y1, y2, type; }; // type: +1 open, -1 close
    vector<Event> events;
    vector<int> ys;

    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        events.push_back({x1, y1, y2, +1});
        events.push_back({x2, y1, y2, -1});
        ys.push_back(y1);
        ys.push_back(y2);
    }

    // Coordinate compression on y-axis
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    auto compress = [&](int v) {
        return (int)(lower_bound(ys.begin(), ys.end(), v) - ys.begin());
    };

    sort(events.begin(), events.end(), [](auto& a, auto& b) {
        return a.x < b.x;
    });

    SegTree seg(ys);
    long long area = 0;
    int prev_x = events[0].x;

    for (auto& [x, y1, y2, type] : events) {
        area += seg.query() * (x - prev_x);
        int lo = compress(y1), hi = compress(y2) - 1;
        seg.update(lo, hi, type);
        prev_x = x;
    }

    cout << area << "\n";
}

Version 2: Explained Version

1D interval union -- step by step:

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    // For each interval [l, r], create two events:
    //   (l, +1) = interval opens at position l
    //   (r, -1) = interval closes at position r
    // Convention: interval covers [l, r), half-open.
    vector<pair<int,int>> events;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        events.push_back({l, +1});
        events.push_back({r, -1});
    }

    // Sort by x-coordinate. At same x, the default pair comparison
    // puts -1 before +1, which processes closes before opens.
    // For union length this is fine (both give same answer).
    sort(events.begin(), events.end());

    long long total = 0;
    int active = 0;  // number of currently open intervals
    int prev_x = 0;  // x-coordinate of the previous event

    for (auto [x, type] : events) {
        // The segment [prev_x, x) has constant coverage = active.
        // If active > 0, this segment is covered.
        if (active > 0)
            total += x - prev_x;

        // Process the event: open or close an interval.
        active += type;
        prev_x = x;
    }

    cout << total << "\n";
}

Maximum overlap -- with careful tie-breaking:

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> events;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        events.push_back({l, +1});
        events.push_back({r, -1});
    }

    // Tie-break: at the same x, process opens (+1) before closes (-1).
    // This ensures that if an interval starts exactly where another ends,
    // both are counted as overlapping at that point.
    // If the problem uses half-open intervals [l, r), process closes first.
    sort(events.begin(), events.end(), [](auto& a, auto& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second; // +1 before -1
    });

    int active = 0, best = 0;
    for (auto [x, type] : events) {
        active += type;
        best = max(best, active);
    }
    cout << best << "\n";
}

Operations Reference

Operation	Time	Space
1D interval union length	$O (n \log n)$	$O (n)$
Maximum overlap count	$O (n \log n)$	$O (n)$
2D rectangle area union (sweep + segment tree)	$O (n \log n)$	$O (n)$
2D rectangle perimeter union	$O (n \log n)$	$O (n)$
Closest pair of points (sweep + BST)	$O (n \log n)$	$O (n)$
Count segment intersections (sweep + BIT/seg tree)	$O ((n + k) \log n)$	$O (n)$
Offline point-in-rectangles (sweep + BIT)	$O ((n + q) \log n)$	$O (n)$

Problem Patterns & Tricks

Pattern 1: 1D Interval Union Length

The foundational sweep. Create $+ 1$ / $- 1$ events, sort, scan. Between consecutive events, add the gap to the answer if active $> 0$ .

cpp

for (auto [x, type] : events) {
    if (active > 0) total += x - prev_x;
    active += type;
    prev_x = x;
}

Problems: CF 1000C -- Covered Points Count (simplified), CSES -- Nested Ranges Count

Pattern 2: Maximum Overlap (Max Active Count)

Same as Pattern 1 but track max(active) instead of length. Careful with tie-breaking: if both endpoints are closed $[l, r]$ , opens go before closes. If half-open $[l, r)$ , closes go before opens.

cpp

active += type;
best = max(best, active);

Problems: CF 1462E -- Close Segments, CF 1606C -- Banknotes

Pattern 3: Covered Points Count (Per-Point Coverage)

Given $n$ intervals, for each integer $k$ from 1 to $n$ , find how many integer points are covered by exactly $k$ intervals. Use events at integer boundaries, or generalize to coordinate-compressed segments with their active counts.

The key idea: between consecutive events the coverage count is constant. So you emit $(gap length, active count)$ pairs and bucket them.

cpp

for (auto [x, type] : events) {
    if (active > 0 && x > prev_x)
        coverage[active] += x - prev_x;
    active += type;
    prev_x = x;
}

Problems: CF 1000C -- Covered Points Count

Pattern 4: 2D Rectangle Area Union

Sweep a vertical line along the $x$ -axis. At each $x$ -event (rectangle opens or closes), update a segment tree on the $y$ -axis. The segment tree tracks, for each $y$ -range, how many rectangles cover it. The root reports the total covered $y$ -length. Multiply by the $x$ -gap to get the area contribution.

Requires coordinate compression on $y$ and a segment tree with a "coverage count" node (not standard lazy -- the cnt field counts how many full-range updates cover a node).

Problems: CF 1000C (2D variant), classic "Area of Union of Rectangles" problems

Pattern 5: Rectangle Perimeter Union

Similar structure to area, but instead of total covered length, count the number of transitions between covered and uncovered along the $y$ -axis. The perimeter contribution at each $x$ -event is:

Horizontal edges: $| new covered length - old covered length |$
Vertical edges: $2 \times (number of covered segments) \times Δ x$

This is trickier and often needs additional bookkeeping in the segment tree.

Problems: Classic problem -- "Perimeter of the Union of Rectangles"

Pattern 6: Closest Pair of Points

Sort points by $x$ . Sweep left to right, maintaining a set of active points ordered by $y$ within a window of width $d$ (current best distance). For each new point, query the set for points with $y$ in $[y - d, y + d]$ and update $d$ . Remove points with $x < current_x - d$ .

cpp

set<pair<int,int>> active; // (y, x) for ordering by y
double d = INF;
int j = 0;
for (int i = 0; i < n; i++) {
    while (pts[i].x - pts[j].x > d)
        active.erase({pts[j].y, pts[j].x}), j++;
    auto it = active.lower_bound({pts[i].y - d, INT_MIN});
    while (it != active.end() && it->first <= pts[i].y + d) {
        d = min(d, dist(pts[i], {it->second, it->first}));
        ++it;
    }
    active.insert({pts[i].y, pts[i].x});
}

Problems: CSES -- Minimum Euclidean Distance, classic "Closest Pair"

Pattern 7: Sweep Line + BIT for Offline Queries

Given rectangles and point queries "how many rectangles contain this point?", sort everything by $x$ . When a rectangle opens, do a range update $+ 1$ on its $y$ -range in a BIT. When it closes, do $- 1$ . When a query arrives at $x_{q}$ , answer with a point query on $y_{q}$ .

Requires all events (opens, closes, queries) sorted by $x$ .

  Sweep + BIT for offline range queries:

  Queries: Q1=[1,5], Q2=[2,7], Q3=[4,9]  (sorted by R)

  Array:  [ a0  a1  a2  a3  a4  a5  a6  a7  a8  a9 ]
  Sweep:    -->  -->  -->  -->  -->
                                 ^
                            sweep reaches R=5
                            --> answer Q1 = BIT.query(5) - BIT.query(0)
                                 -->  -->
                                       ^
                                  sweep reaches R=7
                                  --> answer Q2
                                       -->  -->
                                              ^
                                         sweep reaches R=9
                                         --> answer Q3

  Key: sort queries by right endpoint, sweep left to right,
  answer each query when the sweep reaches its R value.

cpp

sort(all_events.begin(), all_events.end());
for (auto& ev : all_events) {
    if (ev.type == OPEN)  bit.update(ev.y1, ev.y2, +1);
    if (ev.type == CLOSE) bit.update(ev.y1, ev.y2, -1);
    if (ev.type == QUERY) ans[ev.id] = bit.query(ev.y);
}

Problems: CF 1000D, CF 652D

Pattern 8: Counting Intersections Among Segments

Given $n$ horizontal and vertical line segments, count intersections. Sweep along $x$ . When a horizontal segment opens, insert its $y$ -coordinate into a BIT. When it closes, remove it. When a vertical segment is encountered at $x$ , query the BIT for the count of $y$ -values in $[y_{1}, y_{2}]$ .

  Active segment set at each event:

  Event e1 (start seg1):  Active = {seg1}
  Event e2 (start seg2):  Active = {seg1, seg2}
  Event e3 (end seg1,     Active = {seg2, seg3}
            start seg3):
  Event e4 (start seg4):  Active = {seg2, seg3, seg4}
  Event e5 (end seg2,     Active = {seg3}
            end seg4):

  At each event, update active set + query data structure.
  For horizontal/vertical intersections:
    - horizontal start  --> insert y into BIT
    - horizontal end    --> remove y from BIT
    - vertical segment  --> query BIT for count in [y_lo, y_hi]

This is the basis of the Bentley-Ottmann sweep and many computational geometry problems.

Problems: Classic "Count Intersections", variations appear at CF 1800+

Contest Cheat Sheet

+------------------------------------------------------------------+
|                    SWEEP LINE CHEAT SHEET                         |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|   - Union/intersection of intervals or rectangles                |
|   - "How many intervals cover point x?"                          |
|   - Area/perimeter of union of rectangles                        |
|   - Closest pair of points                                       |
|   - Offline geometric queries (points in rectangles)             |
|                                                                  |
| 1D TEMPLATE:                                                     |
|   events: (x, +1) for open, (x, -1) for close                   |
|   sort(events);                                                  |
|   for (auto [x,t] : events) {                                    |
|       if (active > 0) ans += x - prev;                           |
|       active += t; prev = x;                                     |
|   }                                                              |
|                                                                  |
| 2D (RECTANGLES):                                                 |
|   Sweep x-axis, segment tree on y-axis                           |
|   Compress y-coordinates, update ranges on open/close            |
|   area += seg.query() * (x - prev_x)                             |
|                                                                  |
| TIE-BREAKING:                                                    |
|   Closed [l,r]: opens before closes at same x                    |
|   Half-open [l,r): closes before opens at same x                 |
|                                                                  |
| TIME:  O(n log n)     SPACE: O(n)                                |
+------------------------------------------------------------------+

Gotchas & Debugging

Mental Traps

Trap: "Sweep line is for geometry problems."

Sweep line appears in geometry (interval union, rectangle area, line segment intersections) but also in non-geometric problems: processing queries sorted by one parameter while maintaining state for another, event-based simulation, and "contribution of each element to intervals containing it." The geometric framing is helpful but limiting.

Trap: "The sweep itself is the hard part."

Usually the sweep iteration is simple: sort events, iterate. The hard part is: (1) correctly defining the events (what triggers a state change?), (2) defining the state (what do you maintain?), and (3) correctly updating and querying the state at each event. The sweep loop is mechanical once these three things are right.

Trap: "I can just sort by x and then handle y naively."

For many 2D problems, the y-dimension is not trivial. The whole point of sweep line is to maintain an efficient data structure on the y-dimension while sweeping x. If you handle y naively (scan all y for each x event), you have made the sweep into a slow $O (n^{2})$ simulation.

Trap: "I need a sweep line because the problem has intervals."

Not every interval problem needs a sweep. Merging overlapping intervals into non-overlapping groups is just sort-and-merge. Interval scheduling (maximum non-overlapping) is greedy sort-by-right-endpoint. Sweep line is the tool when you need to maintain state about active intervals as you process events -- when the answer depends on the interaction between intervals at each point.

Debug Checklist

Tie-breaking order at same x-coordinate. This is the #1 source of bugs. If intervals are closed $[l, r]$ and you want maximum overlap, opens must come before closes at the same $x$ . If intervals are half-open $[l, r)$ or you are computing union length, the order might not matter -- but think carefully. When in doubt, test both on a small case like $[1, 3]$ and $[3, 5]$ .
Forgetting the last segment. After the loop, active should be 0. If it is not, you missed a close event or have a sign error. Add an assertion: assert(active == 0);.
Integer overflow in area/length. Coordinates up to $10^{9}$ with gaps up to $10^{9}$ and up to $10^{5}$ intervals -- the total length or area can reach $10^{14}$ . Use long long.
Segment tree off-by-one in 2D sweep. The segment tree operates on compressed $y$ -indices. Each leaf $i$ represents the segment $[y_{i}, y_{i + 1})$ . A rectangle with $y$ -range $[y_{1}, y_{2})$ maps to leaf range $[compress (y_{1}), compress (y_{2}) - 1]$ . Off-by-one here silently gives wrong area.
Coordinate compression: forgetting to include all endpoints. You must include both $y_{1}$ and $y_{2}$ of every rectangle (and query points) in the compression array. A missing coordinate distorts ranges.
Events not covering open-and-close correctly. For union length, an interval $[l, r]$ covering integer points should produce events at $l$ (open) and $r + 1$ (close) if you want inclusive coverage. For continuous intervals, events at $l$ and $r$ with half-open convention.
Modifying the segment tree with cnt incorrectly. The rectangle-area segment tree uses a cnt field that is incremented/decremented but never pushed down lazily. It only applies to nodes whose entire range is covered. Do not try to implement standard lazy propagation -- the push-up logic is different (see implementation).
Closest pair: forgetting to remove expired points. When the best distance $d$ shrinks, old points beyond $x - d$ must be removed from the active set. If you forget, the set grows unbounded and queries slow down.

The mistake that teaches

Rectangle union area with same-x events. Sorted by x-coordinate alone, a "remove" event was processed before an "insert" event at the same x. Coverage count briefly dropped for some y-ranges; area calculation was off by a sliver. Fix: add a secondary sort key so insert events precede remove events at the same x. Tie-breaking order in sweep-line events is not cosmetic -- it determines correctness.

CF 1000C Covered Points Count: end+1 overflow. I used half-open intervals with -1 events at end + 1. When the test had end = 10^18, end + 1 overflowed long long. Fix: either restructure to use end (inclusive) with careful point counting, or confirm your integer type has headroom. Half-open intervals are cleaner conceptually but require end + 1, which can overflow -- always check if the coordinate range plus 1 fits.

Debug Drills

Drill 1: Rectangle union area with wrong event ordering.

cpp

struct Event {
    int x, y1, y2, type; // type: +1 = start, -1 = end
};
vector<Event> events;
for (auto& rect : rects) {
    events.push_back({rect.x1, rect.y1, rect.y2, +1});
    events.push_back({rect.x2, rect.y1, rect.y2, -1});
}
sort(events.begin(), events.end(), [](auto& a, auto& b) {
    return a.x < b.x;
});

What's wrong?

When two events have the same x, the sort doesn't define a consistent order. If a "remove" (-1) event is processed before an "add" (+1) event at the same x-coordinate, the segment tree's coverage count can temporarily become invalid (zero when it should still be positive), causing incorrect area computation. Fix: add tie-breaking -- if (a.x == b.x) return a.type > b.type; -- so +1 (insert) events come before -1 (remove) events at the same x.

Drill 2: Coordinate compression off-by-one.

cpp

// Compress y-coordinates
vector<int> ys;
for (auto& rect : rects) {
    ys.push_back(rect.y1);
    ys.push_back(rect.y2);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());

// Segment tree on [0, ys.size() - 1]
// When adding interval [y1, y2]:
int a = lower_bound(ys.begin(), ys.end(), y1) - ys.begin();
int b = lower_bound(ys.begin(), ys.end(), y2) - ys.begin();
seg_tree.update(a, b, +1);

What's wrong?

The segment tree update uses indices [a, b], but each index i in the compressed array represents the interval [ys[i], ys[i+1]), not a single point. Updating [a, b] includes the interval starting at ys[b], which extends to ys[b+1] -- overshooting the actual rectangle's y2. Fix: update the range [a, b - 1] in the segment tree, since the interval [y1, y2) covers compressed indices a through b-1. The covered length for index i is ys[i+1] - ys[i].

Drill 3: Active-set sweep doesn't remove segments properly.

cpp

// Sweep to count horizontal-vertical intersections
multiset<int> active_y; // y-coordinates of active horizontal segments
for (auto& ev : events) {
    if (ev.type == HORIZ_START)
        active_y.insert(ev.y);
    else if (ev.type == HORIZ_END)
        active_y.erase(ev.y);        // BUG
    else { // VERTICAL query
        auto lo = active_y.lower_bound(ev.y1);
        auto hi = active_y.upper_bound(ev.y2);
        answer += distance(lo, hi);
    }
}

What's wrong?

active_y.erase(ev.y) erases all elements with value ev.y from the multiset. If multiple horizontal segments share the same y-coordinate, removing one segment wipes out all of them. Fix: erase only one occurrence: active_y.erase(active_y.find(ev.y));. This removes a single iterator, leaving other copies intact.

Drill 4: Event tie-breaking with pair default sort.

cpp

vector<pair<int,int>> events;
for (auto& seg : segments) {
    events.push_back({seg.l, +1});
    events.push_back({seg.r, -1});
}
sort(events.begin(), events.end());

What's wrong?

When a segment ends at x = 5 and another starts at x = 5, the sort places (-1, +1) events at x = 5 in the order (-1 before +1) because -1 < +1 in the pair's second element. This means the ending segment is processed before the starting segment, causing the coverage count to momentarily drop. If you want the ending point to still be "covered" by both segments at x = 5, you need the +1 event first: sort with {seg.r + 1, -1} (half-open) or custom comparator {x, -type} so +1 comes before -1 at the same x.

Drill 5: Segment tree for area union missing leaf case.

cpp

void update(int node, int lo, int hi, int l, int r, int val) {
    if (l > hi || r < lo) return;
    if (l <= lo && hi <= r) {
        cnt[node] += val;
        if (cnt[node] > 0) len[node] = y[hi+1] - y[lo];
        else len[node] = len[2*node] + len[2*node+1];
        return;
    }
    int mid = (lo + hi) / 2;
    update(2*node, lo, mid, l, r, val);
    update(2*node+1, mid+1, hi, l, r, val);
    if (cnt[node] > 0) len[node] = y[hi+1] - y[lo];
    else len[node] = len[2*node] + len[2*node+1];
}

What's wrong?

The leaf node case is missing. When lo == hi and cnt[node] == 0, the code does len[node] = len[2*node] + len[2*node+1], but leaf nodes have no children -- these accesses are out of bounds or read garbage. Fix: add a leaf check:

cpp

if (cnt[node] > 0) len[node] = y[hi+1] - y[lo];
else if (lo == hi) len[node] = 0;
else len[node] = len[2*node] + len[2*node+1];

Drill 6: Closest pair sweep -- pruning and duplicate points.

cpp

set<pair<int,int>> active; // (y, x) of active points
double best = INF;
sort(pts.begin(), pts.end()); // by x
for (int i = 0, j = 0; i < n; i++) {
    while (pts[i].x - pts[j].x > best)
        active.erase({pts[j].y, pts[j].x}), j++;
    auto lo = active.lower_bound({pts[i].y - best, INT_MIN});
    auto hi = active.upper_bound({pts[i].y + best, INT_MAX});
    for (auto it = lo; it != hi; it++)
        best = min(best, dist(pts[i], {it->second, it->first}));
    active.insert({pts[i].y, pts[i].x});
}

What's wrong?

The pruning condition pts[i].x - pts[j].x > best uses floating-point best compared with integer coordinate differences. If best is, say, 2.5, and two points differ by x = 3, the condition 3 > 2.5 correctly prunes. But the real bug: best is initialized to INF (floating point), but the loop starts pruning from j = 0. On the first iteration, pts[0].x - pts[0].x = 0, which is not > INF, so no pruning happens -- that's fine. The actual issue is that best starts as floating-point infinity, and the initial comparisons work, but if points have duplicate x-coordinates, multiple points at the same x won't be compared against each other because active.insert uses (y, x) pairs, and two points with the same (y, x) will collide in the set, losing one point. Fix: use a multiset or add a unique tiebreaker (point index).

Self-Test

Before moving on, verify you can answer these without referencing the material above:

[ ] Define an "event" in sweep-line context -- what is an event, what triggers it, and what information does it carry?
[ ] Write pseudocode for 1D interval union: given $n$ intervals $[l_{i}, r_{i}]$ , compute the total length of their union using a sweep.
[ ] State the tie-breaking rule for interval union: if two events share the same coordinate, which is processed first? Does the answer change for open vs. closed endpoints?
[ ] Explain what data structure the 2D rectangle-area-union sweep requires on the $y$ -axis, and why a simple counter is insufficient.
[ ] Give one example of a non-geometric problem where a sweep-line approach applies.
[ ] Describe why coordinate compression is needed when the coordinate range is $[0, 10^{9}]$ but only $O (n)$ distinct values appear.
[ ] Explain the invariant maintained during a 1D interval-union sweep: what does the active counter represent at any point during the sweep?

Practice Problems

Rating Progression

CF Rating	What to Master
1200	Event-based thinking: convert intervals into (start, end) events, sort, and sweep with a counter to find maximum overlap. 1D event sweep: sort intervals by start, process +1/-1 events to count overlaps.
1500	2D sweep: rectangle union area via sweep line + segment tree with lazy propagation for covered length; coordinate compression. Sweep + BIT/segment tree for nested segments, point-in-how-many-intervals.
1800	Line segment intersection detection (Bentley-Ottmann simplified); sweep with a `std::set` as the active structure; handling degenerate cases (vertical segments, shared endpoints). Closest pair in O(n log n).
2100	3D sweep (sweep plane reducing to 2D sweep line); persistent sweep structures; combining sweep with offline techniques (CDQ + sweep for 3D problems). Sweep + coordinate compression for large coordinates, sweep + persistent structures.

#	Problem	Source	Difficulty	Key Idea
1	Covered Points Count	CF 1000C	1700	1D sweep, track active count per segment
2	Nested Ranges Count	CSES	1700	Sweep + BIT for containment counting
3	Meeting Place	CF 629D	1700	Sweep line on intervals
4	Rectangles	CF 1196F	1800	2D sweep, counting coverage
5	Points and Segments	CSES	1800	Sweep with BIT for point-in-segment
6	Mushrooms After Rain	CF 1749D	1900	Sweep + contribution counting
7	Segments	CF 652D	1800	Sweep + BIT for nested segments
8	Minimum Euclidean Distance	CSES	2000	Closest pair sweep
9	Area of Union of Rectangles	Library Checker	2100	Full 2D sweep + segment tree
10	Segments Intersection	CF 1401E	2100	Sweep + advanced counting

Sweep Line ​

Contents ​

Intuition ​

Visual Walkthrough ​

The Invariant ​

When to Reach for This ​

What the Code Won't Teach You ​

C++ STL Reference ​

Implementation (Contest-Ready) ​

Event Tie-Breaking at the Same Coordinate ​

Version 1: Minimal Contest Template ​

Version 2: Explained Version ​

Operations Reference ​

Problem Patterns & Tricks ​

Pattern 1: 1D Interval Union Length ​

Pattern 2: Maximum Overlap (Max Active Count) ​

Pattern 3: Covered Points Count (Per-Point Coverage) ​

Pattern 4: 2D Rectangle Area Union ​

Pattern 5: Rectangle Perimeter Union ​

Pattern 6: Closest Pair of Points ​

Pattern 7: Sweep Line + BIT for Offline Queries ​

Pattern 8: Counting Intersections Among Segments ​

Contest Cheat Sheet ​

Gotchas & Debugging ​

Mental Traps ​

Debug Checklist ​

The mistake that teaches ​

Debug Drills ​

Self-Test ​

Practice Problems ​

Further Reading ​

Sweep Line

Contents

Intuition

Visual Walkthrough

The Invariant

When to Reach for This

What the Code Won't Teach You

C++ STL Reference

Implementation (Contest-Ready)

Event Tie-Breaking at the Same Coordinate

Version 1: Minimal Contest Template

Version 2: Explained Version

Operations Reference

Problem Patterns & Tricks

Pattern 1: 1D Interval Union Length

Pattern 2: Maximum Overlap (Max Active Count)

Pattern 3: Covered Points Count (Per-Point Coverage)

Pattern 4: 2D Rectangle Area Union

Pattern 5: Rectangle Perimeter Union

Pattern 6: Closest Pair of Points

Pattern 7: Sweep Line + BIT for Offline Queries

Pattern 8: Counting Intersections Among Segments

Contest Cheat Sheet

Gotchas & Debugging

Mental Traps

Debug Checklist

The mistake that teaches

Debug Drills

Self-Test

Practice Problems

Further Reading