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

### Prerequisites

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

Resources
cp-algo

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

1. Update index $i$ to value $v$
2. Report the minimum and the number of occurences of the minimum on a range $[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 $(\texttt{val}, \texttt{cnt})$, where $\texttt{val}$ is the minimum value and $\texttt{cnt}$ is the number occurences of the minimum value.

If node $c$ has two children $a$ and $b$, then

• if $a.\texttt{val} < b.\texttt{val}$, then $c = a$
• if $a.\texttt{val} > b.\texttt{val}$, then $c = b$
• if $a.\texttt{val} = b.\texttt{val}$, then $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 nodesNode merge(Node a, Node b) {	if (a.val < b.val) {		return a;

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

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