PrevNext
Has Not Appeared
 0/6

Counting Minimums with Segment Tree

Authors: Benjamin Qi, Dustin Miao

Querying for the minimum and number of occurences of minimum in a range

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

We would like a data structure that can efficiently handle two types of operations:

  1. Update index ii to value vv
  2. Report the minimum and the number of occurences of the minimum on a range [l,r][l, r]

We can use a normal segment tree to handle range queries, but slightly modify each node and the merge operation. Let each node be a pair of values (val,cnt)(\texttt{val}, \texttt{cnt}), where val\texttt{val} is the minimum value and cnt\texttt{cnt} is the number occurences of the minimum value.

If node cc has two children aa and bb, then

  • if a.val<b.vala.\texttt{val} < b.\texttt{val}, then c=ac = a
  • if a.val>b.vala.\texttt{val} > b.\texttt{val}, then c=bc = b
  • if a.val=b.vala.\texttt{val} = b.\texttt{val}, then c={a.val,a.cnt+b.cnt}c = \{a.\texttt{val}, a.\texttt{cnt} + b.\texttt{cnt}\}

Implementation

C++

const int MAXN = 2e5;
struct Node {
int val = INT32_MAX, cnt = 1;
} tree[2 * MAXN];
// combines two segment tree nodes
Node merge(Node a, Node b) {
if (a.val < b.val) {
return a;

Solution - Area of Rectangles

Hint 1

Hint 2

We can use techniques introduced in Range Queries with Sweep Line

We sweep from left to right over the xx-coordinates, maintaining two events for each rectangle: one for the left boundary and one for the right boundary. Maintain a Lazy Segment Tree over the yy-coordinates.

  • When we run into a left boundary of some rectangle with yy-coordinates (y0,y1)(y_0, y_1), increase each index i[y0,y1]i \in [y_0, y_1] by 1
  • When we run into a right boundary of some rectangle with yy-coordinates (y0,y1)(y_0, y_1), decrease each index i[y0,y1]i \in [y_0, y_1] by 1

Then, for each xx, we simply need to count the number of non-zero indices which corresponds to indices that are covered by at least one rectangle. How can we do this?

Instead of counting the area covered by at least one rectangle, let's count the amount of space covered by no rectangles. We can subtract this amount from the total number of indices to get the value we want.

We can use a Segment Tree that counts the number of occurences of the minimum value. Because the minimum value is at least zero (there can't be a negative number of rectangles at a position) the number of uncovered squares is equal to the number of squares with value 0.

Implementation

C++

#include <bits/stdc++.h>
using namespace std;
const int MAXX = 1e6;
const int MAXN = 2 * MAXX + 1;
struct Event {
int t, x, y0, y1;
// t = 1 for left bound, -1 for right bound
bool operator<(const Event &e) { return x < e.x; }

Problems

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsDP
mBITNormal
IOIHard
HRHard
Show TagsLazy SegTree
CFVery Hard

Optional: Permutation Tree

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!

PrevNext