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 – read through 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

Solution

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