Кесинди дарагы

Кесинди дарагы: кесиндидеги сумма жана чекитти жаңылоо O(log n) убакытта.

Префикстик суммалар «кесиндидеги суммага» O(1) убакытта жооп берет, бирок массив ӨЗГӨРӨ баштаганда эле бузулат: бир жаңылоо — бардык префикстерди кайра эсептөө. Кесинди дарагы суроону да, жаңылоону да O(log n) убакытта жасайт. Идея: массивдин үстүнө экилик дарак курулат; ар бир чоку өз кесиндисинин суммасын сактайт. Тамыр — бүт массивдин суммасы, жалбырактар — өзүнчө элементтер. • элементти жаңылоо жалбырактан тамырга чейинки жолдогу чокуларга гана тиет — алар O(log n); • [l, r] суроосу дарактын O(log n) даяр кесиндисине ажырайт.

Өзүңүз байкап көрүңүз — кодду өзгөртсө болот

#include <iostream>
#include <vector>
#include <string>

int n;
std::vector<long long> tree;

void update(int v, int tl, int tr, int pos, long long val) {
    if (tl == tr) {
        tree[v] = val;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) update(2 * v, tl, tm, pos, val);
    else update(2 * v + 1, tm + 1, tr, pos, val);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

long long query(int v, int tl, int tr, int l, int r) {
    if (r < tl || tr < l) return 0;          // отрезки не пересекаются
    if (l <= tl && tr <= r) return tree[v];  // отрезок дерева целиком внутри
    int tm = (tl + tr) / 2;
    return query(2 * v, tl, tm, l, r) + query(2 * v + 1, tm + 1, tr, l, r);
}

int main() {
    int q;
    std::cin >> n >> q;
    tree.assign(4 * n, 0);

for (int i = 1; i <= n; i++) {
        long long x;
        std::cin >> x;
        update(1, 1, n, i, x);
    }

while (q--) {
        std::string type;
        std::cin >> type;
        if (type == "set") {
            int pos;
            long long val;
            std::cin >> pos >> val;
            update(1, 1, n, pos, val);
        } else {
            int l, r;
            std::cin >> l >> r;
            std::cout << query(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

Киргизүү маалыматтары (мисал — өзгөртсө болот)

Киргизиңиз: 5 3, массив 1 2 3 4 5, андан кийин: sum 2 4 / set 3 10 / sum 2 4

Мисалды иштетиңиз: [2,4] суммасы адегенде 9, set 3 10 кийин 16 болот. Кодду кантип окуу керек: • v чокусу [tl, tr] кесиндисине жооп берет; балдары — кесиндинин жарымдары, номерлери 2v жана 2v+1; • өлчөмү 4n болгон tree массиви бүт даракты кепилдик менен батырат; • query кесилишпеген кесиндилер үчүн 0 кайтарат — нөл сумма үчүн нейтралдуу. Кесинди дарагы — конструктор: + белгисин min же max менен (жана нейтралдуу элементти чексиздик менен) алмаштырыңыз — минимум/максимум суроолорун аласыз. «Жалкоо» жаңылоолору бар өркүндөтүлгөн версиясы бүтүн кесиндилерди O(log n) убакытта өзгөртө алат — андай маселеге туш болгондо үйрөнүңүз.

Тапшырма: даракты кесиндидеги МАКСИМУМГА кайра жасаңыз (үч оңдоо: операция, нейтралдуу элемент, чыгаруу) жана өз мисалыңызда текшериңиз. Сабакты өттүм деп белгилеңиз.