↵
Изначально у меня была идея сделать многослойную декомпозицию, где на первом слое блоки имеют размер $(\sqrt{N}\)$, на втором — $(\sqrt{\sqrt{N}}\)$ и так далее. Думал, что получится интересная альтернатива стандартным подходам. Но когда начал изучать архивы Codeforces, оказалось, что про подобное уже писали, но сейчас статью не нашел.↵
↵
В итоге я решил отказаться от корней и посмотреть в сторону степеней двойки, но не через Sparse Table (который не поддерживает обновления и требует много памяти), а через фиксированную сетку слоев, совмещенную с логикой двоичного подъема. Назвал эту штуку SBLD (Segment Binary Lifting Data-structure). Получился гибрид, который выполняет запросы и точечные обновления за $2 \log N$) действий в худшем случае, используя строгие O(N) памяти (ровно 2N элементов вместе с базовым массивом).↵
↵
### Устройство сетки слоев↵
↵
Структура не хранит все пересекающиеся отрезки. Массив разбивается на независимые блоки на каждом слое `i`, где длина блока равна $2^{i+1}$:↵
↵
```text↵
Слой 2 (len=8): [----------------------- ans -----------------------]↵
Слой 1 (len=4): [--------- ans ---------] [--------- ans ---------]↵
Слой 0 (len=2): [--- ans ---] [--- ans ---] [--- ans ---] [--- ans ---]↵
base_a (len=1): [ L0 ] [ L1 ] [ L2 ] [ L3 ] [ L4 ] [ L5 ] [ L6 ] [ L7 ]↵
```↵
↵
Суммарная память по всем слоям: $N/2 + N/4 + N/8 + \dots = O(N)$. Вместе с исходным массивом `base_a` (который можно считать слоем -1) выходит ровно $2N$ элементов. Построение линейное — просто попарно объединяем соседей снизу вверх.↵
↵
### Алгоритм запроса↵
↵
Мы ищем ответ на полуинтервале $[L, R)$. Стартуем в точке `cur_l = L` и жадно двигаемся вправо по степеням двойки, выбирая максимально возможный шаг. ↵
↵
Размер шага $i$ (длина шага $2^{i+1}$) ограничен двумя факторами:↵
1. **Выравнивание левой границы**: мы можем сделать шаг на слой $i$, только если текущий индекс `cur_l` делится на $2^{i+1}$. Это ограничение вычисляется через `__builtin_ctz(cur_l)`.↵
2. **Расстояние до правой границы**: чтобы не вылететь за пределы $R$, шаг должен быть $\le R - cur\_l$. Это ограничение определяется старшим битом: `31 - __builtin_clz(R - cur_l)`.↵
↵
Итоговая формула выбора слоя на текущей итерации:↵
$$i = \min(\text{ctz}(cur\_l), \; 31 - \text{clz}(R - cur\_l)) - 1$$↵
↵
Если $i < 0$, значит, мы не можем взять даже блок длины 2 (например, когда `cur_l` нечетный или остался всего 1 элемент). В этом случае берем значение напрямую из `base_a` и сдвигаем `cur_l` на 1.↵
↵
#### Почему это работает за $2 \log N$ шагов?↵
Процесс можно разделить на две фазы. Сначала идет подъем: пока `cur_l` выравнивается, значения `ctz` строго растут, и шаги увеличиваются (максимум $\log N$ итераций). Затем мы упираемся в ограничение по расстоянию до $R$, и начинается спуск: куски уменьшаются, что эквивалентно разложению длины оставшегося отрезка в двоичную систему (еще максимум $\log N$ шагов).↵
↵
### Главное отличие и продвинутые кейсы↵
↵
Важное свойство SBLD — мы всегда двигаемся строго **слева направо**. Классическое итеративное дерево отрезков снизу-вверх сжимает границы с двух сторон одновременно. Из-за этого на **некоммутативных операциях** (например, динамическое перемножение матриц на отрезке) там приходится аккуратно следить за порядком склейки аккумуляторов. В SBLD порядок операций никогда не нарушается, поэтому некоммутативные структуры работают «из коробки» за $O(D^3 \log N)$.↵
↵
Также вместо одного значения в блоке можно хранить отсортированный `std::vector`, мержить их при построении и получить Merge Sort Tree на плоских слоях. Память составит $O(N \log N)$ без оверхеда на структуру дерева и указатели, а запросы будут работать через `upper_bound` за $O(\log^2 N)$.↵
↵
### Код на C++ (пример для матриц 2х2)↵
↵
```cpp↵
#include <vector>↵
#include <algorithm>↵
#include <iostream>↵
↵
using namespace std;↵
↵
const int MOD = 1e9 + 7;↵
struct Matrix {↵
long long mat;↵
Matrix() {↵
mat = 1; mat = 0;↵
mat = 0; mat = 1;↵
}↵
};↵
↵
typedef Matrix T;↵
↵
T combine(const T& a, const T& b) {↵
T res;↵
res.mat = (a.mat * b.mat + a.mat * b.mat) % MOD;↵
res.mat = (a.mat * b.mat + a.mat * b.mat) % MOD;↵
res.mat = (a.mat * b.mat + a.mat * b.mat) % MOD;↵
res.mat = (a.mat * b.mat + a.mat * b.mat
↵
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 -----------------------]<br>↵
Layer 1 (len=4): [--------- ans ---------] [--------- ans ---------]<br>↵
Layer 0 (len=2): [--- ans ---] [--- ans ---] [--- ans ---] [--- ans ---]<br>↵
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)↵
↵
<pre><code>↵
#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<T> base_a;↵
vector<vector<T>> ans;↵
↵
SBLD(vector<T> a) {↵
n = a.size();↵
base_a = std::move(a); ↵
max_log = (n > 0) ? (32
ans.resize(max_log);↵
↵
if (n == 0) return;↵
↵
ans.resize((n + 1) / 2, NEUTRAL);↵
for (int i = 0; i < n; i++) {↵
ans[i >> 1] = combine(ans
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
}↵
}↵
}↵
↵
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
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;↵
}↵
};↵
↵
Конечно, стандартное итеративное ДО на массиве пишется короче и на базовых операциях вроде суммы выиграет по константе за счет симметричного сжатия границ. Но для тяжелых или некоммутативных объектов, где критически важен строгий порядок объединения слева-направо, такая явная разбивка по слоям двоичного подъема выглядит довольно нативно. ↵
↵
Кто-нибудь кодил подобные структуры или тестировал их производительность на реальных задачах? Интересно услышать мысли в комментариях.↵
↵
↵
↵
Upd: урааа я не зря потратил столько времени разбираться с MathJax, это было очень трудно))))
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 :)↵
