Initially, I had an idea to create a multi-layered decomposition structure where the first layer would have block sizes of $$$(\sqrt{N})$$$, the second layer $$$(\sqrt{\sqrt{N}})$$$, and so on. I thought it would be an interesting alternative to standard approaches. However, after exploring the Codeforces archives, I found out that a similar concept (Layered SQRT-decomposition) had already been thoroughly discussed in previous blogs, so reinventing it didn't make much sense.

Consequently, I decided to move away from square roots and look into powers of two instead. Rather than using a Sparse Table (which doesn't support updates and consumes too much memory), I opted for a rigid grid of layers combined with binary lifting logic. I named this structure SBLD (Segment Binary Lifting Data-structure). The result is a hybrid that processes range queries and point updates in $$$(2\log N)$$$ operations in the worst case, utilizing strict O(N) memory (exactly 2N elements including the base array).

Layer Grid Architecture

The structure does not store all overlapping intervals. Instead, the array is partitioned into independent blocks on each layer i, where the block length equals $$$(2^{i+1})$$$:

Layer 2 (len=8): [----------------------- ans -----------------------]
Layer 1 (len=4): [--------- ans ---------] [--------- ans ---------]
Layer 0 (len=2): [--- ans ---] [--- ans ---] [--- ans ---] [--- ans ---]
base_a (len=1): [ L0 ] [ L1 ] [ L2 ] [ L3 ] [ L4 ] [ L5 ] [ L6 ] [ L7 ]

Summing up the memory across all layers yields (N/2 + N/4 + N/8 + \dots = O(N)). Together with the initial array base_a (which can be conceptually treated as layer -1), it takes exactly 2N elements. Construction is linear—we simply merge adjacent pairs bottom-up.

Query Algorithm

We search for the answer on a half-open interval ([L, R)). We start at cur_l = L and greedily move to the right using powers of two, picking the maximum possible step size at each turn.

The step size i (where the step length is (2^{i+1})) is bounded by two constraints: 1. Left Boundary Alignment: We can only make a step to layer i if the current index cur_l is divisible by (2^{i+1}). This constraint is computed via __builtin_ctz(cur_l). 2. Distance to the Right Boundary: To prevent overshooting past R, the step must be (\le R — cur_l). This constraint is determined by the highest set bit: 31 - __builtin_clz(R - cur_l).

Thus, the formula for selecting the layer on the current iteration is: [i = \min(\text{ctz}(cur_l), \; 31 — \text{clz}(R — cur_l)) — 1]

If i < 0, it means we cannot even take a block of length 2 (for instance, when cur_l is odd or only 1 element remains). In this scenario, we fetch the value directly from base_a and increment cur_l by 1.

Why does it run in (2 \log N) steps?

The process can be split into two distinct phases. First is the ascent phase: while cur_l is aligning itself, the ctz values strictly increase, causing the step sizes to grow (at most (\log N) iterations). Then, we hit the distance constraint to R, initiating the descent phase: the blocks shrink down, which is equivalent to decomposing the remaining length into its binary representation (at most another (\log N) steps).

Key Difference and Advanced Use Cases

The most vital property of SBLD is that we always move strictly from left to right. The classical iterative bottom-up segment tree compresses boundaries from both sides simultaneously. Because of this, dealing with non-commutative operations (like dynamic matrix multiplication on a range) requires meticulously tracking the order in which left and right accumulators are merged. In SBLD, the operational order is never violated, meaning non-commutative structures work flawlessly out of the box in (O(D^3 \log N)) time.

Furthermore, instead of storing a single value per block, you can store a sorted std::vector, merging them during construction to get a Merge Sort Tree on flat layers. The memory footprint will be a strict (O(N \log N)) without any overhead from tree pointers or node structures, and range queries can be answered using upper_bound in (O(\log^2 N)) time.

C++ Code (Example for 2x2 Matrices)

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;
struct Matrix {
    long long mat[2][2];
    Matrix() {
        mat[0][0] = 1; mat[0][1] = 0;
        mat[1][0] = 0; mat[1][1] = 1;
    }
};

typedef Matrix T;

T combine(const T& a, const T& b) {
    T res;
    res.mat[0][0] = (a.mat[0][0] * b.mat[0][0] + a.mat[0][1] * b.mat[1][0]) % MOD;
    res.mat[0][1] = (a.mat[0][0] * b.mat[0][1] + a.mat[0][1] * b.mat[1][1]) % MOD;
    res.mat[1][0] = (a.mat[1][0] * b.mat[0][0] + a.mat[1][1] * b.mat[1][0]) % MOD;
    res.mat[1][1] = (a.mat[1][0] * b.mat[0][1] + a.mat[1][1] * b.mat[1][1]) % MOD;
    return res;
}

const T NEUTRAL = Matrix(); 

struct SBLD {
    int n;
    int max_log;
    vector base_a;
    vector> ans;

    SBLD(vector a) {
        n = a.size();
        base_a = std::move(a); 
        max_log = (n > 0) ? (32 — __builtin_clz(n)) : 0;
        ans.resize(max_log);

        if (n == 0) return;

        ans[0].resize((n + 1) / 2, NEUTRAL);
        for (int i = 0; i < n; i++) {
            ans[0][i >> 1] = combine(ans[0][i >> 1], base_a[i]);
        }

        for (int i = 1; i < max_log; i++) {
            int sz = (ans[i - 1].size() + 1) / 2;
            ans[i].resize(sz, NEUTRAL);
            for (int j = 0; j < ans[i - 1].size(); j++) {
                ans[i][j >> 1] = combine(ans[i][j >> 1], ans[i — 1][j]);
            }
        }
    }

    void update(int idx, T val) {
        base_a[idx] = std::move(val);
        
        int l0 = idx >> 1;
        T left0 = base_a[l0 * 2];
        T right0 = (l0 * 2 + 1 < n) ? base_a[l0 * 2 + 1] : NEUTRAL;
        ans[0][l0] = combine(left0, right0);

        for (int i = 1; i < max_log; i++) {
            int cur_l = idx >> (i + 1);
            int left_son = cur_l * 2;
            int right_son = left_son + 1;
            
            T val_left = ans[i — 1][left_son];
            T val_right = (right_son < ans[i - 1].size()) ? ans[i - 1][right_son] : NEUTRAL;
            
            ans[i][cur_l] = combine(val_left, val_right);
        }
    }

    T query(int L, int R) { 
        T cur_ans = NEUTRAL;
        int cur_l = L;

        while (cur_l < R) {
            int limit_r = 31 - __builtin_clz(R - cur_l);
            int limit_l = (cur_l == 0) ? limit_r : __builtin_ctz(cur_l);
            
            int i = min(limit_l, limit_r) - 1;
            
            if (i < 0) {
                cur_ans = combine(cur_ans, base_a[cur_l]);
                cur_l += 1;
            } else {
                cur_ans = combine(cur_ans, ans[i][cur_l >> (i + 1)]);
                cur_l += (1 << (i + 1));
            }
        }
        return cur_ans;
    }
};

Admittedly, a standard iterative bottom-up segment tree takes fewer lines to implement and will likely beat this structure in terms of constant factor on basic operations (like range sum queries) due to its symmetric boundary compression. However, for complex or non-commutative objects where a strict left-to-right merging order is vital, this explicit binary lifting layer split feels highly intuitive.

Has anyone coded similar structures or tested their performance on real problems? I would love to hear your thoughts in the comments. UPD: I got absolutely exhausted trying to configure MathJax for the Codeforces parser, so if some formulas still look a bit weird, my bad — hope the core idea is clear anyway :) UPD: Thanks to the community for the active feedback and interest in my structure! Your input helped a lot in making it much more polished and well-defined.