C++ segment tree build O(NlogN), query O(logN)
I believe my implementation is (almost) correct. Somehow i can not pass the last test case where there are all 1s and 2s. What\'s annoying is that I can not see
I believe my implementation is (almost) correct. Somehow i can not pass the last test case where there are all 1s and 2s. What\'s annoying is that I can not see the full input of this test case.\nAt least for all the leading queries of the last test case, my answer is correct.\n\n\n```\nclass SegmentNode {\npublic:\n    int start;\n    int end;\n    int majority;\n    int count;\n    SegmentNode *left;\n    SegmentNode *right;\n    SegmentNode(int s, int e, int m, int c) {\n        start = s;\n        end = e;\n        majority = m;\n        count = c;\n        left = nullptr;\n        right = nullptr;\n    }\n};\n    \nclass MajorityChecker {\npublic:\n    MajorityChecker(vector<int>& A) {\n        rootNode = build(A, 0, A.size() - 1);\n        // cout << rootNode->majority << " " << rootNode->count << endl;\n        this->arr = A;\n    }\n    \n    int query(int start, int end, int threshold) {\n        pair<int, int> res = queryHelper(rootNode, start, end);\n        if (res.second >= threshold) {\n            return res.first;\n        }\n        return -1;\n    }\nprivate:\n    SegmentNode *rootNode;\n    \n    vector<int> arr;\n    \n    SegmentNode *build(vector<int>& A, int start, int end) {\n        SegmentNode *root = new SegmentNode(start, end, A[start], 1);\n        if (start == end) {\n            return root;\n        }\n        // go left and right\n        int mid = start + (end - start) / 2;\n        SegmentNode *leftNode = build(A, start, mid);\n        SegmentNode *rightNode = build(A, mid + 1, end);\n        root->left = leftNode;\n        root->right = rightNode;\n        \n        // update majority and count\n        if (leftNode->majority == rightNode->majority) {\n            root->majority = leftNode->majority;\n            root->count = leftNode->count + rightNode->count;\n            return root;\n        }\n        \n        if (leftNode->count > rightNode->count) {\n            root->majority = leftNode->majority;\n            root->count = leftNode->count + getCount(A, mid + 1, end, root->majority);\n        } else {\n            root->majority = rightNode->majority;\n            root->count = rightNode->count + getCount(A, start, mid, root->majority);\n        }\n        \n        return root;\n    }\n    \n    pair<int, int> queryHelper(SegmentNode *root, int start, int end) {\n        if (start == root->start && end == root->end) {\n            return {root->majority, root->count};\n        }\n        // go left/right\n        int mid = root->start + (root->end - root->start) / 2;\n        if (end <= mid) {\n            return queryHelper(root->left, start, end);\n        } else if (start >= mid + 1) {\n            return queryHelper(root->right, start, end);\n        } else {\n            pair<int, int> leftRes = queryHelper(root->left, start, mid);\n            pair<int, int> rightRes = queryHelper(root->right, mid + 1, end);\n            if (leftRes.first == rightRes.first) {\n                return {leftRes.first, leftRes.second + rightRes.second};\n            } else if (leftRes.second > rightRes.second) {\n                return {leftRes.first, leftRes.second + getCount(arr, mid + 1, end, leftRes.first)};\n            } else {\n                return {rightRes.first, rightRes.second + getCount(arr, start, mid, rightRes.first)};\n            }\n        }\n    }\n    \n    int getCount(vector<int>& A, int start, int end, int num) {\n        int count = 0;\n        for (int i = start; i <= end; i++) {\n            if (A[i] == num) {\n                count++;\n            }\n        }\n        return count;\n    }\n};\n```
[]