this is a data structure which I briefly saw mentioned in a cf blog, but has literally zero mentions in the english language outside of that. however it seems to be quite popular in china for a number of reasons. here is an explanation + sample implementation

Principle

When querying the sum of information over the interval [l,r], we find the LCA of the nodes representing [l,l], and [r,r] on the segment tree. Let this node p represent the interval [L,R]. We will discover some very interesting properties: (1) The interval [L,R] must contain [l,r] . Obviously, because it is both an ancestor of l and an ancestor of r. (2) The interval [l,r] must cross the midpoint of [L,R]. Since p is the LCA of l and r, this means p's left child is an ancestor of l but not r, and p's right child is an ancestor of r but not l. Therefore, l must lie in the interval [L,mid], and r must lie in (mid, R]

With these two properties, we can reduce the query complexity to O(1).

Implementation

key idea: for each node with range [L, R], let its midpoint be M. Recursively build the segtree, at each level creating a suffix "sum" (whatever operation you want) array for the region [L, M], and a prefix sum array for the region (M, R]. that way if you have a point to the left and a point to the right you can combine the suffix and prefix sums respectively in O(merge cost) = O(1) for many types of operations. by the master theorem the total work done, T(n) = 2T(n/2) + O(n) = O(n log n).

one issue though: how do we find the lca of [l,l] and [r,r]? answer: build the cat tree with the heap representation, make it a perfect power of 2. with this construction, the lca of 2 nodes x,y in a heap = longest common prefix of the bits of x and y. This is equal to lcp(x,y)=x>>digits[x^y] (where digits[i] = floor(log2(i)) + 1), or in c++ we have int lcp = k - __lg(l^r) - 1;.

with that we have enough information to build the cat tree. here is an example implementation:

#include <bits/stdc++.h>
using namespace std;

template<class T, class Merge>
struct CatTree {
    int N, n, k;
    vector<T> a; vector<vector<T>> st;
    Merge merge;

    CatTree(const vector<T> &A, Merge merge_op, T base = T()) {
        N = A.size(), n = 1, k = 0, a = A, merge = merge_op;
        while (n < N) n *= 2, k++;

        a.resize(n, base); st.assign(max(1,k), vector<T>(n, base));
        if (n>1) build(0, 0, n-1);
    }

    void build(int depth, int l, int r) {
        if (l == r) return;
        int m = l + (r-l) / 2;

        st[depth][m] = a[m];
        for (int i = m-1; i >= l; i--) st[depth][i] = merge(a[i], st[depth][i+1]);

        st[depth][m+1] = a[m+1];
        for (int i = m+2; i <= r; i++) st[depth][i] = merge(st[depth][i-1], a[i]);

        build(depth+1, l, m); build(depth+1, m+1, r);
    }

    T query(int l, int r) {
        if (l == r) return a[l];
        int lcp = k - __lg(l^r) - 1;
        return merge(st[lcp][l], st[lcp][r]);
    }
};

example usage:

int n; cin >> n;
vector<int> a(n+1, 0); for (int i = 1; i <= n; i++) cin >> a[i];
auto merge = [](int a, int b) {return a|b;};
CatTree<int, decltype(merge)> st = CatTree(a, merge);

hope someone finds this useful. also glad to share a data structure that i haven't ever seen mentioned anywhere in english