# Online Majority Element In Subarray
**Difficulty:** HARD
[External](https://leetcode.com/problems/online-majority-element-in-subarray)
Canonical: https://scaleengineer.com/dsa/problems/online-majority-element-in-subarray
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Binary Indexed Tree, Segment Tree
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix)
---
## Problem
Design a data structure that efficiently finds the **majority element** of a given subarray.

The **majority element** of a subarray is an element that occurs `threshold` times or more in the subarray.

Implementing the `MajorityChecker` class:

* `MajorityChecker(int[] arr)` Initializes the instance of the class with the given array `arr`.
* `int query(int left, int right, int threshold)` returns the element in the subarray `arr[left...right]` that occurs at least `threshold` times, or `-1` if no such element exists.

**Example 1:**

**Input**
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
**Output**
[null, 1, -1, 2]

**Explanation**
MajorityChecker majorityChecker = new MajorityChecker([1, 1, 2, 2, 1, 1]);
majorityChecker.query(0, 5, 4); // return 1
majorityChecker.query(0, 3, 3); // return -1
majorityChecker.query(2, 3, 2); // return 2

**Constraints:**

* `1 <= arr.length <= 2 * 104`
* `1 <= arr[i] <= 2 * 104`
* `0 <= left <= right < arr.length`
* `threshold <= right - left + 1`
* `2 * threshold > right - left + 1`
* At most `104` calls will be made to `query`.

# Approaches
## Brute Force Iteration
The most straightforward approach is to simulate the process directly for each query. We can iterate through the given subarray `arr[left...right]`, count the occurrences of each number using a hash map, and then check if any number's count meets the `threshold`.
**Time:** O(N) for each query, where `N = right - left + 1`. With `Q` queries, the total time complexity is `O(Q * L)` where `L` is the maximum length of the array. This is too slow for the given constraints. · **Space:** O(U) for each query, where `U` is the number of unique elements in the subarray `arr[left...right]`. In the worst case, `U` can be `O(right - left + 1)`.
**Pros:** Simple to understand and implement.; Requires no complex data structures or algorithms.; No preprocessing time and minimal space usage in the constructor.
**Cons:** Very slow for large subarrays or a high number of queries.; Time complexity per query is linear to the size of the subarray, which can be up to the entire array length.; Likely to result in a "Time Limit Exceeded" error for the given constraints.
### Explanation
This method involves no preprocessing in the constructor; it simply stores a reference to the input array. All the work is done within the `query` method.

For each call to `query(left, right, threshold)`, we perform the following steps:
1.  Initialize a new hash map to serve as a frequency counter.
2.  Loop through the array `arr` from the `left` index to the `right` index, inclusive.
3.  In each iteration, we take the element `arr[i]` and update its count in the hash map.
4.  Once the loop is complete, the hash map contains the exact frequency of every unique element in the subarray `arr[left...right]`.
5.  We then iterate through the key-value pairs in the hash map.
6.  For each element, we compare its frequency with the `threshold`.
7.  If we find an element whose frequency is at least `threshold`, we have found the majority element and return it.
8.  If we iterate through all the unique elements and none meet the condition, it means no majority element exists, so we return -1.

```java
class MajorityChecker {
    private int[] arr;

    public MajorityChecker(int[] arr) {
        this.arr = arr;
    }

    public int query(int left, int right, int threshold) {
        java.util.Map<Integer, Integer> counts = new java.util.HashMap<>();
        for (int i = left; i <= right; i++) {
            counts.put(arr[i], counts.getOrDefault(arr[i], 0) + 1);
        }
        for (java.util.Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() >= threshold) {
                return entry.getKey();
            }
        }
        return -1;
    }
}
```
### Algorithm
- In the `query(left, right, threshold)` method:
- Create a `HashMap<Integer, Integer>` to store the frequency of each number in the subarray `arr[left...right]`.
- Iterate through the subarray from index `left` to `right`.
- For each element `arr[i]`, increment its count in the hash map.
- After populating the map, iterate through its entries.
- If any element's count is greater than or equal to `threshold`, return that element.
- If no such element is found after checking all entries, return -1.

## Square Root Decomposition
A better approach than brute-force is to use Square Root Decomposition. This technique balances preprocessing time and query time. We divide the array into `sqrt(L)` blocks. For a query, we can handle the parts of the range that fall into full blocks using precomputed information, and the parts that are in partial blocks are handled naively. This reduces the number of elements we need to inspect closely, leading to a list of `O(sqrt(L))` candidates for the majority element.
**Time:** O(L) for preprocessing. Each query takes `O(sqrt(L) * log L)` time because we check `O(sqrt(L))` candidates and each check takes `O(log L)`. This is efficient enough to pass the given constraints. · **Space:** O(L) to store the `locs` map and `O(sqrt(L))` for block-related pre-computation. Total space is `O(L)`.
**Pros:** Significantly faster than the brute-force approach.; It is a deterministic algorithm, always providing the correct answer.
**Cons:** More complex to implement than the brute-force or randomized approaches.; Query time is slower than logarithmic solutions.; The constant factors involved can be large.
### Explanation
This method improves upon the brute-force approach by pre-calculating some information to speed up queries.

**Preprocessing in `MajorityChecker(arr)`:**
1.  First, we create a hash map `locs` that maps each number to a sorted list of its indices in the array. This will be crucial for quickly counting occurrences in a range.
2.  We then set a block size, typically `B = sqrt(arr.length)`.
3.  The array is conceptually divided into `arr.length / B` blocks.
4.  For each of these blocks, we run the Boyer-Moore Voting algorithm to find a majority candidate and store these candidates.

**Answering a `query(left, right, threshold)`:**
1.  The query range `[left, right]` will typically span across multiple blocks. It can be seen as a partial block at the start, a series of full blocks, and a partial block at the end.
2.  We generate a set of potential candidates for the majority element of the entire range `[left, right]`. The true majority element must be among these candidates. The candidates are:
    *   Every element in the start partial block (from `left` to the end of its block).
    *   Every element in the end partial block (from the start of its block to `right`).
    *   The pre-calculated majority candidates of all the full blocks between the start and end blocks.
3.  The total number of candidates generated this way is on the order of `O(sqrt(L))`, where `L` is the array length.
4.  For each of these candidates, we must verify if it is indeed the majority element. We find its true frequency in the range `[left, right]` by using our `locs` map. With the sorted list of indices, we can find the count in `O(log L)` time using two binary searches (one for `left` and one for `right`).
5.  If we find a candidate whose count is `>= threshold`, we return it. If we check all candidates and none satisfy the condition, we return -1.
### Algorithm
- **Preprocessing (Constructor):**
  - Create a map `locs` where `locs.get(x)` returns a sorted list of all indices where `x` appears in the original array.
  - Divide the array into `B = sqrt(L)` blocks, each of size `B`.
  - For each block, pre-calculate its majority candidate using the Boyer-Moore Voting algorithm and store it.
- **Query `(left, right, threshold)`:**
  - The query range `[left, right]` covers some partial blocks at the ends and some full blocks in the middle.
  - Collect a set of candidates for the majority element. These are:
    1. All elements in the partial start and end blocks.
    2. The pre-calculated majority candidates for all the full blocks in between.
  - This results in `O(sqrt(L))` candidates.
  - For each unique candidate, calculate its true frequency in `[left, right]` using the `locs` map and binary search. This takes `O(log L)`.
  - If any candidate's frequency is `>= threshold`, return it.
  - If none are found, return -1.

## Randomized Sampling
A very efficient and simpler-to-implement approach leverages the problem's specific constraint: `2 * threshold > right - left + 1`. This means the majority element, if it exists, must appear in more than 50% of the subarray. Therefore, a randomly selected element from the subarray has a greater than 50% chance of being the majority element. By sampling a few random elements and checking if they meet the threshold, we can find the majority element with very high probability.
**Time:** O(L) for preprocessing. Each query takes `O(K * log L)` time. Since `K` is a small constant, this is effectively `O(log L)` per query. · **Space:** O(L) to store the `locs` map, where `L` is the length of the array.
**Pros:** Very fast query time, effectively `O(log L)`.; Simpler to implement than other advanced data structures like segment trees.; The probability of error can be made arbitrarily small by increasing the number of trials `K`.
**Cons:** The algorithm is probabilistic. There is a very small chance of a false negative (returning -1 when a majority element exists).; The probability of failure for one query is `(1/p)^K` where `p` is the proportion of the majority element. Given the problem constraint, `p > 0.5`, so the failure probability is `< (1/2)^K`, which is negligible for `K=20`.
### Explanation
This approach combines preprocessing with a randomized query strategy.

**Preprocessing in `MajorityChecker(arr)`:**
We iterate through the input array `arr` once to build a hash map `locs`. This map stores each unique number from `arr` as a key, and its value is a sorted list of all indices at which the number appears. This structure allows us to quickly count the occurrences of any number within an arbitrary range `[left, right]`.

**Answering a `query(left, right, threshold)`:**
1.  We set a constant number of iterations, say `K=20`. This number determines the trade-off between speed and accuracy. A higher `K` means a lower probability of error.
2.  We loop `K` times. In each iteration, we pick a random index from the query range `[left, right]`.
3.  The element at this random index becomes our `candidate` for the majority element.
4.  We then verify this candidate. Using our pre-computed `locs` map, we find the list of indices for the `candidate`. We perform binary search on this list to find the count of indices that are between `left` and `right`.
5.  If this count is `>= threshold`, we have successfully found the majority element and can immediately return it.
6.  If the loop finishes after `K` trials and we haven't returned, we conclude that no majority element exists and return -1. The probability of this conclusion being wrong is extremely low.

```java
class MajorityChecker {
    private final int[] arr;
    private final java.util.Map<Integer, java.util.List<Integer>> locs;
    private final java.util.Random random;

    public MajorityChecker(int[] arr) {
        this.arr = arr;
        this.locs = new java.util.HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            locs.computeIfAbsent(arr[i], k -> new java.util.ArrayList<>()).add(i);
        }
        this.random = new java.util.Random();
    }

    public int query(int left, int right, int threshold) {
        int K = 20; // Number of random trials
        for (int i = 0; i < K; i++) {
            int randIdx = left + random.nextInt(right - left + 1);
            int candidate = arr[randIdx];
            
            java.util.List<Integer> indices = locs.get(candidate);
            int start = java.util.Collections.binarySearch(indices, left);
            if (start < 0) start = -start - 1;
            
            int end = java.util.Collections.binarySearch(indices, right);
            if (end < 0) end = -end - 1; else end++;
            
            if (end - start >= threshold) {
                return candidate;
            }
        }
        return -1;
    }
}
```
### Algorithm
- **Preprocessing (Constructor):**
  - Create a hash map `locs` where `locs.get(x)` returns a sorted list of all indices where `x` appears in the original array. This takes `O(L)` time and space.
- **Query `(left, right, threshold)`:**
  - Perform a small, fixed number of trials, e.g., `K = 20`.
  - In each trial:
    1. Pick a random index `rand_idx` from the range `[left, right]`.
    2. Let `candidate = arr[rand_idx]`.
    3. Use the `locs` map to find the true count of `candidate` in `arr[left...right]`. This is done by performing two binary searches on `locs.get(candidate)` to find the number of its indices that fall within `[left, right]`.
    4. If the count is `>= threshold`, we have found the majority element. Return `candidate`.
  - If all `K` trials complete without finding a majority element, return -1.

## Segment Tree with Boyer-Moore Voting
The most efficient and deterministic solution involves a powerful data structure, the Segment Tree. We can augment the segment tree to find a majority candidate for any given range based on the Boyer-Moore Voting algorithm. The key idea is that the majority element of a combined range must be the majority element of one of the sub-ranges. This allows us to find a single candidate for any query range in logarithmic time.
**Time:** O(L) for preprocessing. Each query takes `O(log L)` time. · **Space:** O(L) for the `locs` map and the segment tree.
**Pros:** Guaranteed to be correct (deterministic).; Highly efficient with logarithmic time complexity per query.; A standard and robust technique for range query problems.
**Cons:** The most complex approach to implement correctly.; Has a higher space overhead due to the segment tree, which typically requires `4*L` space.
### Explanation
This approach provides a deterministic `O(log L)` query time solution by combining a Segment Tree with the logic of the Boyer-Moore Voting algorithm.

**Data Structures:**
1.  **Segment Tree:** A tree where each node represents a range of the input array. Each node will store a `(candidate, count)` pair, representing the majority candidate and its Boyer-Moore score for that range.
2.  **Index Map (`locs`):** Same as in previous approaches, a map from each number to a sorted list of its indices, used for final verification.

**Preprocessing in `MajorityChecker(arr)`:**
1.  The `locs` map is built in `O(L)` time.
2.  A segment tree is built over the array `arr`. The construction is recursive:
    *   A leaf node corresponding to `arr[i]` stores `(candidate=arr[i], count=1)`.
    *   An internal node is built by merging its left and right children. The `merge(left_node, right_node)` function implements the core logic: if `left_node.candidate == right_node.candidate`, their counts are added. If they differ, the candidate with the higher count becomes the new candidate, and its new count is the difference of the children's counts. If counts are equal, there is no clear winner.
    *   The entire tree is built in `O(L)` time.

**Answering a `query(left, right, threshold)`:**
1.  We perform a range query on the segment tree for the interval `[left, right]`. This operation traverses the tree and combines the nodes that make up the query range using the same `merge` logic. This process efficiently finds the Boyer-Moore candidate for the specific range `[left, right]` in `O(log L)` time.
2.  The query returns a single `candidate`.
3.  This candidate is the only possibility for the majority element. We must verify its actual frequency. We use the `locs` map and binary search to count its occurrences in `[left, right]` in `O(log L)` time.
4.  If the actual count is `>= threshold`, we return the candidate. Otherwise, no majority element exists, and we return -1.

```java
class MajorityChecker {
    private static class Node {
        int candidate;
        int count;
        Node(int c, int v) { candidate = c; count = v; }
    }
    private final int[] arr;
    private final java.util.Map<Integer, java.util.List<Integer>> locs;
    private final Node[] tree;

    public MajorityChecker(int[] arr) {
        this.arr = arr;
        this.locs = new java.util.HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            locs.computeIfAbsent(arr[i], k -> new java.util.ArrayList<>()).add(i);
        }
        this.tree = new Node[4 * arr.length];
        build(1, 0, arr.length - 1);
    }

    private Node merge(Node left, Node right) {
        if (left.candidate == right.candidate) return new Node(left.candidate, left.count + right.count);
        if (left.count > right.count) return new Node(left.candidate, left.count - right.count);
        if (right.count > left.count) return new Node(right.candidate, right.count - left.count);
        return new Node(0, 0); // Sentinel for no candidate
    }

    private void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = new Node(arr[start], 1);
            return;
        }
        int mid = start + (end - start) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }

    private Node queryTree(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return new Node(0, 0);
        if (l <= start && end <= r) return tree[node];
        int mid = start + (end - start) / 2;
        Node p1 = queryTree(2 * node, start, mid, l, r);
        Node p2 = queryTree(2 * node + 1, mid + 1, end, l, r);
        return merge(p1, p2);
    }
    
    private int countInRange(int val, int left, int right) {
        java.util.List<Integer> indices = locs.get(val);
        if (indices == null) return 0;
        int startIdx = java.util.Collections.binarySearch(indices, left);
        if (startIdx < 0) startIdx = -startIdx - 1;
        int endIdx = java.util.Collections.binarySearch(indices, right);
        if (endIdx < 0) endIdx = -endIdx - 1; else endIdx++;
        return endIdx - startIdx;
    }

    public int query(int left, int right, int threshold) {
        Node result = queryTree(1, 0, arr.length - 1, left, right);
        int candidate = result.candidate;
        if (candidate == 0) return -1;
        if (countInRange(candidate, left, right) >= threshold) {
            return candidate;
        }
        return -1;
    }
}
```
### Algorithm
- **Node Structure:** Define a `Node` class to store `(candidate, count)`.
- **Preprocessing (Constructor):**
  1. Build the `locs` map to store indices of each number, for final verification.
  2. Build a segment tree over the array. A leaf node for `arr[i]` is `(arr[i], 1)`. An internal node is formed by `merging` its children.
- **Merge Logic:** The merge operation combines two nodes, simulating Boyer-Moore. If candidates are the same, counts are added. If different, the candidate with the larger count wins, and its new count is the difference of the two counts.
- **Query `(left, right, threshold)`:**
  1. Perform a range query on the segment tree for `[left, right]`. This combines multiple nodes using the merge logic and returns a final `(candidate, count)` pair in `O(log L)` time.
  2. This `candidate` is the only possible majority element.
  3. Verify the candidate by finding its true frequency in `[left, right]` using the `locs` map and binary search (`O(log L)`).
  4. If the frequency is `>= threshold`, return the candidate; otherwise, return -1.

# Solutions
### Java

```java
class Node { int l , r ; int x , cnt ; } class SegmentTree { private Node [] tr ; private int [] nums ; public SegmentTree ( int [] nums ) { int n = nums . length ; this . nums = nums ; tr = new Node [ n << 2 ]; for ( int i = 0 ; i < tr . length ; ++ i ) { tr [ i ] = new Node (); } build ( 1 , 1 , n ); } private void build ( int u , int l , int r ) { tr [ u ]. l = l ; tr [ u ]. r = r ; if ( l == r ) { tr [ u ]. x = nums [ l - 1 ]; tr [ u ]. cnt = 1 ; return ; } int mid = ( l + r ) >> 1 ; build ( u << 1 , l , mid ); build ( u << 1 | 1 , mid + 1 , r ); pushup ( u ); } public int [] query ( int u , int l , int r ) { if ( tr [ u ]. l >= l && tr [ u ]. r <= r ) { return new int [] { tr [ u ]. x , tr [ u ]. cnt }; } int mid = ( tr [ u ]. l + tr [ u ]. r ) >> 1 ; if ( r <= mid ) { return query ( u << 1 , l , r ); } if ( l > mid ) { return query ( u << 1 | 1 , l , r ); } var left = query ( u << 1 , l , r ); var right = query ( u << 1 | 1 , l , r ); if ( left [ 0 ] == right [ 0 ]) { left [ 1 ] += right [ 1 ]; } else if ( left [ 1 ] >= right [ 1 ]) { left [ 1 ] -= right [ 1 ]; } else { right [ 1 ] -= left [ 1 ]; left = right ; } return left ; } private void pushup ( int u ) { if ( tr [ u << 1 ]. x == tr [ u << 1 | 1 ]. x ) { tr [ u ]. x = tr [ u << 1 ]. x ; tr [ u ]. cnt = tr [ u << 1 ]. cnt + tr [ u << 1 | 1 ]. cnt ; } else if ( tr [ u << 1 ]. cnt >= tr [ u << 1 | 1 ]. cnt ) { tr [ u ]. x = tr [ u << 1 ]. x ; tr [ u ]. cnt = tr [ u << 1 ]. cnt - tr [ u << 1 | 1 ]. cnt ; } else { tr [ u ]. x = tr [ u << 1 | 1 ]. x ; tr [ u ]. cnt = tr [ u << 1 | 1 ]. cnt - tr [ u << 1 ]. cnt ; } } } class MajorityChecker { private SegmentTree tree ; private Map < Integer , List < Integer >> d = new HashMap <>(); public MajorityChecker ( int [] arr ) { tree = new SegmentTree ( arr ); for ( int i = 0 ; i < arr . length ; ++ i ) { d . computeIfAbsent ( arr [ i ], k -> new ArrayList <>()). add ( i ); } } public int query ( int left , int right , int threshold ) { int x = tree . query ( 1 , left + 1 , right + 1 )[ 0 ]; int l = search ( d . get ( x ), left ); int r = search ( d . get ( x ), right + 1 ); return r - l >= threshold ? x : - 1 ; } private int search ( List < Integer > arr , int x ) { int left = 0 , right = arr . size (); while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( arr . get ( mid ) >= x ) { right = mid ; } else { left = mid + 1 ; } } return left ; } } /** * Your MajorityChecker object will be instantiated and called as such: * MajorityChecker obj = new MajorityChecker(arr); * int param_1 = obj.query(left,right,threshold); */
```

### Python

```python
class Node : __slots__ = ( "l" , "r" , "x" , "cnt" ) def __init__ ( self ): self . l = self . r = 0 self . x = self . cnt = 0 class SegmentTree : def __init__ ( self , nums ): self . nums = nums n = len ( nums ) self . tr = [ Node () for _ in range ( n << 2 )] self . build ( 1 , 1 , n ) def build ( self , u , l , r ): self . tr [ u ]. l , self . tr [ u ]. r = l , r if l == r : self . tr [ u ]. x = self . nums [ l - 1 ] self . tr [ u ]. cnt = 1 return mid = ( l + r ) >> 1 self . build ( u << 1 , l , mid ) self . build ( u << 1 | 1 , mid + 1 , r ) self . pushup ( u ) def query ( self , u , l , r ): if self . tr [ u ]. l >= l and self . tr [ u ]. r <= r : return self . tr [ u ]. x , self . tr [ u ]. cnt mid = ( self . tr [ u ]. l + self . tr [ u ]. r ) >> 1 if r <= mid : return self . query ( u << 1 , l , r ) if l > mid : return self . query ( u << 1 | 1 , l , r ) x1 , cnt1 = self . query ( u << 1 , l , r ) x2 , cnt2 = self . query ( u << 1 | 1 , l , r ) if x1 == x2 : return x1 , cnt1 + cnt2 if cnt1 >= cnt2 : return x1 , cnt1 - cnt2 else : return x2 , cnt2 - cnt1 def pushup ( self , u ): if self . tr [ u << 1 ]. x == self . tr [ u << 1 | 1 ]. x : self . tr [ u ]. x = self . tr [ u << 1 ]. x self . tr [ u ]. cnt = self . tr [ u << 1 ]. cnt + self . tr [ u << 1 | 1 ]. cnt elif self . tr [ u << 1 ]. cnt >= self . tr [ u << 1 | 1 ]. cnt : self . tr [ u ]. x = self . tr [ u << 1 ]. x self . tr [ u ]. cnt = self . tr [ u << 1 ]. cnt - self . tr [ u << 1 | 1 ]. cnt else : self . tr [ u ]. x = self . tr [ u << 1 | 1 ]. x self . tr [ u ]. cnt = self . tr [ u << 1 | 1 ]. cnt - self . tr [ u << 1 ]. cnt class MajorityChecker : def __init__ ( self , arr : List [ int ]): self . tree = SegmentTree ( arr ) self . d = defaultdict ( list ) for i , x in enumerate ( arr ): self . d [ x ]. append ( i ) def query ( self , left : int , right : int , threshold : int ) -> int : x , _ = self . tree . query ( 1 , left + 1 , right + 1 ) l = bisect_left ( self . d [ x ], left ) r = bisect_left ( self . d [ x ], right + 1 ) return x if r - l >= threshold else - 1 # Your MajorityChecker object will be instantiated and called as such: # obj = MajorityChecker(arr) # param_1 = obj.query(left,right,threshold)
```

### CPP

```cpp
class Node { public: int l = 0 , r = 0 ; int x = 0 , cnt = 0 ; }; using pii = pair < int , int > ; class SegmentTree { public: SegmentTree ( vector < int >& nums ) { this -> nums = nums ; int n = nums . size (); tr . resize ( n << 2 ); for ( int i = 0 ; i < tr . size (); ++ i ) { tr [ i ] = new Node (); } build ( 1 , 1 , n ); } pii query ( int u , int l , int r ) { if ( tr [ u ] -> l >= l && tr [ u ] -> r <= r ) { return { tr [ u ] -> x , tr [ u ] -> cnt }; } int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ; if ( r <= mid ) { return query ( u << 1 , l , r ); } if ( l > mid ) { return query ( u << 1 | 1 , l , r ); } auto left = query ( u << 1 , l , r ); auto right = query ( u << 1 | 1 , l , r ); if ( left . first == right . first ) { left . second += right . second ; } else if ( left . second >= right . second ) { left . second -= right . second ; } else { right . second -= left . second ; left = right ; } return left ; } private: vector < Node *> tr ; vector < int > nums ; void build ( int u , int l , int r ) { tr [ u ] -> l = l ; tr [ u ] -> r = r ; if ( l == r ) { tr [ u ] -> x = nums [ l - 1 ]; tr [ u ] -> cnt = 1 ; return ; } int mid = ( l + r ) >> 1 ; build ( u << 1 , l , mid ); build ( u << 1 | 1 , mid + 1 , r ); pushup ( u ); } void pushup ( int u ) { if ( tr [ u << 1 ] -> x == tr [ u << 1 | 1 ] -> x ) { tr [ u ] -> x = tr [ u << 1 ] -> x ; tr [ u ] -> cnt = tr [ u << 1 ] -> cnt + tr [ u << 1 | 1 ] -> cnt ; } else if ( tr [ u << 1 ] -> cnt >= tr [ u << 1 | 1 ] -> cnt ) { tr [ u ] -> x = tr [ u << 1 ] -> x ; tr [ u ] -> cnt = tr [ u << 1 ] -> cnt - tr [ u << 1 | 1 ] -> cnt ; } else { tr [ u ] -> x = tr [ u << 1 | 1 ] -> x ; tr [ u ] -> cnt = tr [ u << 1 | 1 ] -> cnt - tr [ u << 1 ] -> cnt ; } } }; class MajorityChecker { public: MajorityChecker ( vector < int >& arr ) { tree = new SegmentTree ( arr ); for ( int i = 0 ; i < arr . size (); ++ i ) { d [ arr [ i ]]. push_back ( i ); } } int query ( int left , int right , int threshold ) { int x = tree -> query ( 1 , left + 1 , right + 1 ). first ; auto l = lower_bound ( d [ x ]. begin (), d [ x ]. end (), left ); auto r = lower_bound ( d [ x ]. begin (), d [ x ]. end (), right + 1 ); return r - l >= threshold ? x : - 1 ; } private: unordered_map < int , vector < int >> d ; SegmentTree * tree ; }; /** * Your MajorityChecker object will be instantiated and called as such: * MajorityChecker* obj = new MajorityChecker(arr); * int param_1 = obj->query(left,right,threshold); */
```