Persistent Segment Tree Solution (C++ with explanation/100% Time/100% Memory)
(Note: the word "set" in this context actually means multiset, which also stores the count for each element)\n\nConsider that we have a sequence of sets T[0..n+
(Note: the word "set" in this context actually means multiset, which also stores the count for each element)\n\nConsider that we have a sequence of sets `T[0..n+1]` that `T[i+1]` is the value set of `arr[0..i]`, where `T[0]` is an empty set. We can easily get the value set of any interval `arr[l..r]` by computing difference between `T[r+1]` and `T[l]`. This somehow resembles the use of partial sum.\n\nThe above is what persistent segment tree exactly does. Note that the `i`-th element in a tree no longer represents the `i`-th element in the sequence `arr`, but the count of element `i` present in the tree.\n\nA key observation is that if there exists a number occurring at least `threshold` times in an interval, where `2 * threshold > |interval|`, the size of either left or right child must be at least `threshold`.\n\nSpace Complexity: `O(nlogn)`\nTime Complexity: `O(nlogn)` preprocess, `O(logn)` query\n\nCode:\n```c++\nclass MajorityChecker {\nprivate:\n  // tree node of a persistent segment tree\n  struct Node {\n    Node* l;\n    Node* r;\n    // #values corresponded to this node in the set if the node is a leaf\n    // #elements in this subtree otherwise\n    int count;\n  };\n  vector<int> elems;\n  vector<Node> nodes;\n  vector<Node*> roots;\n  int range;\npublic:\n  MajorityChecker(vector<int>& arr) {\n    ios_base::sync_with_stdio(false);\n    cin.tie(nullptr);\n    // shrink the input range by mapping them into [0, range)\n    vector<int> rank(20001);\n    for (auto val : arr)\n      rank[val] = 1;\n    auto nums = 0;\n    elems.reserve(arr.size());\n    for (auto i = 1; i <= 20000; ++i)\n      if (rank[i]) {\n        rank[i] = nums++;\n        elems.emplace_back(i); // memorize the original number so that we can recover it later\n      }\n    // calculate the tree height\n    auto height = 0;\n    while ((1 << height) < nums)\n      ++height;\n    range = 1 << height;\n    // calculate #node needed:\n    //   2*range nodes for the initial tree (full binary tree with few extra nodes)\n    //   (height+1) nodes for each update (there are |arr| updates)\n    nodes.resize((range << 1) + arr.size() * (height + 1));\n    // construct the initial tree, currently no element in the tree\n    for (auto i = 0; i < range; ++i) {\n      nodes[i].l = &nodes[(i << 1) + 1];\n      nodes[i].r = &nodes[(i << 1) + 2];\n    }\n    // a helper variable for allocating nodes\n    auto cur = range << 1;\n    roots.resize(arr.size() + 1);\n    // roots[0] stores the empty set\n    // roots[i+1] stores the value set from arr[0] to arr[i]\n    roots[0] = &nodes[0];\n    // insert arr[i] into the set roots[i+1]\n    for (auto i = 0; i < arr.size(); ++i) {\n      // update operation\n      // value represented by a node is in [lower, upper)\n      auto val = rank[arr[i]];\n      auto nodOld = roots[i];\n      auto nodNew = &roots[i + 1];\n      auto lower = 0;\n      auto upper = range;\n      while (lower + 1 != upper) {\n        auto middle = (lower + upper) >> 1;\n        nodes[cur].l = nodOld->l;\n        nodes[cur].r = nodOld->r;\n        nodes[cur].count = nodOld->count + 1;\n        *nodNew = &nodes[cur++];\n        if (val < middle) {\n          nodOld = nodOld->l;\n          nodNew = &(*nodNew)->l;\n          upper = middle;\n        }\n        else {\n          nodOld = nodOld->r;\n          nodNew = &(*nodNew)->r;\n          lower = middle;\n        }\n      }\n      nodes[cur].l = nodOld->l;\n      nodes[cur].r = nodOld->r;\n      nodes[cur].count = nodOld->count + 1;\n      *nodNew = &nodes[cur++];\n    }\n  }\n\n  int query(int left, int right, int threshold) {\n    // query operation\n    // the value set of arr[left..right] is roots[right+1]-roots[left]\n    auto nodLow = roots[left];\n    auto nodUpp = roots[right + 1];\n    auto lower = 0;\n    auto upper = range;\n    while (lower + 1 != upper) {\n      auto middle = (lower + upper) >> 1;\n      if (nodUpp->l->count - nodLow->l->count >= threshold) {\n        nodLow = nodLow->l;\n        nodUpp = nodUpp->l;\n        upper = middle;\n      }\n      else if (nodUpp->r->count - nodLow->r->count >= threshold) {\n        nodLow = nodLow->r;\n        nodUpp = nodUpp->r;\n        lower = middle;\n      }\n      else\n        return -1;\n    }\n    return elems[lower]; // recover the original number from elems\n  }\n};\n```
[]