Disjoint Sparse Table: версия без дополнения до степени двойки

#include <bits/stdc++.h>

using namespace std;

struct MaxCntAccumulator {
    int segmentMax;
    int maxCnt;

    MaxCntAccumulator() // Neutral element
        : segmentMax(-1), maxCnt(0) {}

    MaxCntAccumulator(int arrayElem) // from a single value
        : segmentMax(arrayElem), maxCnt(1) {}

    MaxCntAccumulator(int segmentMax, int maxCnt)
        : segmentMax(segmentMax), maxCnt(maxCnt) {}

    MaxCntAccumulator operator+(const MaxCntAccumulator &other) { // accumulating function
        if (segmentMax > other.segmentMax) {
            return *this;
        } else if (segmentMax < other.segmentMax) {
            return other;
        } else {
            return MaxCntAccumulator(segmentMax, maxCnt + other.maxCnt);
        }
    }
};

template<typename AccumType>
struct DisjointSparseTable {
    static const int MAXN = 1000001;
    static const int LOG = 20;

    AccumType sparseTable[LOG][MAXN];

    template<typename InputType>
    DisjointSparseTable(const vector<InputType> &arr) {
        int n = arr.size();
        int height = highestBit(n) + 1;
        for (int lvl = 0; lvl < height; lvl++) {
            int curLen = (1 << lvl);
            for (int center = curLen; center < n + curLen; center += 2 * curLen) {
                AccumType prefAccum;
                for (int i = center; i < center + curLen && i <= n; i++) {
                    sparseTable[lvl][i] = prefAccum;
                    if (i != n) {
                        prefAccum = prefAccum + AccumType(arr[i]);
                    }
                }
                for (int i = min(n - 1, center - 1); i >= center - curLen; i--) {
                    sparseTable[lvl][i] = AccumType(arr[i]) + sparseTable[lvl][i + 1];
                }
            }
        }
    }

    int highestBit(int number) {
        return 31 - __builtin_clz(number);
    }

    AccumType query(int left, int right) { // [left, right)
        int lvl = highestBit(left ^ right);
        return sparseTable[lvl][left] + sparseTable[lvl][right];
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int &elem : arr) {
        cin >> elem;
    }
    DisjointSparseTable<MaxCntAccumulator> maxCntSparse(arr);

    int queriesNumber;
    cin >> queriesNumber;
    for (int i = 0; i < queriesNumber; i++) {
        int left, right;
        cin >> left >> right;
        left--;
        MaxCntAccumulator result = maxCntSparse.query(left, right);
        cout << result.segmentMax << ' ' << result.maxCnt << '\n';
    }
    return 0;
}