Недавно я участвовал в соревновании и там было задание решающееся через дерево отрезков. Я написал SBLD и не пожалел: оно легко написалось без багов, компактно уложилось и зашло. Всем так советую) Вот короткий код(сравните с множеством функций в ДО): vector st(60); st[0] = 1; for (int i = 1; i < 60; i++) { st[i] = st[i — 1] * 2; } vector<vector> sbld(log2(n)+1, vector(n)); vector clz(n), ctz(n); for (int i = 0; i < n; i++) { sbld[0][i] = a[i]; } for (int i = 1; i < sbld.size(); i++) { for (int j = 0; j < n; j+=st[i]) { sbld[i][j] = sbld[i — 1][j];

    if (j + st[i - 1] < n) {
       sbld[i][j] = min(sbld[i - 1][j + st[i-1]], sbld[i][j]);
       clz[j] = i;
    }
}

} for (int i = 1; i < n; i++) { ctz[i] = ctz[i / 2] + 1; } vector mn(n);

for (int i = 0; i < n; i++) { ll cur = i, cur_ans = 1e16; if (ans[i] == -1) { continue; } while (cur != ans[i]) { ll ind = min(clz[cur], ctz[ans[i]-cur]-1); cur_ans = min(cur_ans, sbld[ind][cur]); cur += st[ind]; } mn[i] = cur_ans; }