uniolympiads English

Δέντρο διαστημάτων (segment tree)

Ερωτήματα σε διαστήματα για οποιαδήποτε προσεταιριστική πράξη, με αλλαγές σημείων ή, με lazy propagation, ολόκληρων διαστημάτων. O(log⁡n)O(\log n) ανά πράξη.

Πότε

Το Fenwick δεν φτάνει όταν η πράξη δεν έχει αντίστροφο (ελάχιστο, μέγιστο, gcd) ή όταν ο κόμβος πρέπει να κρατά κάτι σύνθετο, όπως «μέγιστο άθροισμα υποδιαστήματος».

Η ιδέα

Ένα πλήρες δυαδικό δέντρο πάνω στον πίνακα: τα φύλλα είναι τα στοιχεία, κάθε εσωτερικός κόμβος κρατά τον συνδυασμό των δύο παιδιών του. Οποιοδήποτε [l,r][l, r] σπάει σε O(log⁡n)O(\log n) κόμβους, το πολύ δύο ανά επίπεδο.

Η πρώτη εκδοχή είναι επαναληπτική, από κάτω προς τα πάνω: φύλλα στις θέσεις n,…,2n−1n, \dots, 2n-1, γονέας του ii το ⌊i/2⌋\lfloor i/2 \rfloor. Δουλεύει για κάθε nn, όχι μόνο για δυνάμεις του 2. Κρατά δύο αποτελέσματα, left και right, ώστε να μένει σωστή και για πράξεις που δεν αντιμετατίθενται (π.χ. σύνθεση συναρτήσεων).

Για άλλη πράξη αλλάζεις μόνο το combine και το IDENTITY: για άθροισμα 00 και a + b, για μέγιστο LLONG_MIN και max.

Lazy propagation. Όταν η αλλαγή αφορά ολόκληρο διάστημα («πρόσθεσε vv στο [l,r][l, r]»), δεν κατεβαίνουμε ως τα φύλλα. Όπου ένας κόμβος καλύπτεται ολόκληρος, ενημερώνουμε το άθροισμά του κατά v⋅(μηˊκος)v \cdot (\text{μήκος}) και σημειώνουμε στο lazy ότι τα παιδιά του χρωστούν +v+v. Το χρέος περνά στα παιδιά (push) μόνο όταν χρειαστεί να κατέβουμε.

Παγίδες

  • Η αναδρομική εκδοχή θέλει πίνακα 4n4n, όχι 2n2n.
  • Στο Range Updates and Sums υπάρχει και «θέσε όλο το διάστημα ίσο με vv». Τότε το lazy κρατά ζευγάρι (θέση, πρόσθεση) και η θέση ακυρώνει ό,τι πρόσθεση υπήρχε από κάτω. Η σειρά εφαρμογής στο apply είναι όλη η δυσκολία.
  • Στο Hotel Queries δεν θέλεις τιμή αλλά θέση: «το πρώτο δωμάτιο με χωρητικότητα ≥x\ge x». Κατεβαίνεις από τη ρίζα, πάντα αριστερά αν το αριστερό παιδί έχει μέγιστο ≥x\ge x. Είναι O(log⁡n)O(\log n), όχι O(log⁡2n)O(\log^2 n) με δυαδική αναζήτηση από πάνω.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/segment-tree.cpp
// Segment tree, iterative (bottom-up), for any associative operation with an identity.
// Here: point assignment and range minimum on [l, r], 0-indexed. O(log n) per operation.
// Change combine() and IDENTITY for sums, max, gcd, ...

struct SegmentTree {
    static constexpr ll IDENTITY = LLONG_MAX;
    int n;
    vector<ll> t;

    static ll combine(ll a, ll b) {
        return min(a, b);
    }

    SegmentTree(const vector<ll>& a) : n(a.size()), t(2 * a.size(), IDENTITY) {
        for (int i = 0; i < n; i++) {
            t[n + i] = a[i];
        }
        for (int i = n - 1; i >= 1; i--) {
            t[i] = combine(t[2 * i], t[2 * i + 1]);
        }
    }

    void set(int i, ll v) {
        i += n;
        t[i] = v;
        while (i > 1) {
            i /= 2;
            t[i] = combine(t[2 * i], t[2 * i + 1]);
        }
    }

    ll query(int l, int r) {
        ll left = IDENTITY;
        ll right = IDENTITY;
        l += n;
        r += n + 1;
        while (l < r) {
            if (l & 1) {
                left = combine(left, t[l]);
                l++;
            }
            if (r & 1) {
                r--;
                right = combine(t[r], right);
            }
            l /= 2;
            r /= 2;
        }
        return combine(left, right);
    }
};

Ελέγχθηκε σε 500 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

cpp/lazy-segment-tree.cpp
// Segment tree with lazy propagation: add v to every element of [l, r], sum of [l, r].
// 0-indexed, recursive, O(log n) per operation.
// lazy[node] = value already added to tree[node] but not yet pushed to its children.

struct LazySegmentTree {
    int n;
    vector<ll> tree;
    vector<ll> lazy;

    LazySegmentTree(const vector<ll>& a) : n(a.size()), tree(4 * a.size() + 4, 0), lazy(4 * a.size() + 4, 0) {
        if (n > 0) {
            build(a, 1, 0, n - 1);
        }
    }

    void build(const vector<ll>& a, int node, int l, int r) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(a, 2 * node, l, mid);
        build(a, 2 * node + 1, mid + 1, r);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void apply(int node, int l, int r, ll v) {
        tree[node] += v * (r - l + 1);
        lazy[node] += v;
    }

    void push(int node, int l, int r) {
        if (lazy[node] != 0) {
            int mid = (l + r) / 2;
            apply(2 * node, l, mid, lazy[node]);
            apply(2 * node + 1, mid + 1, r, lazy[node]);
            lazy[node] = 0;
        }
    }

    void add(int ql, int qr, ll v, int node, int l, int r) {
        if (qr < l || r < ql) {
            return;
        }
        if (ql <= l && r <= qr) {
            apply(node, l, r, v);
            return;
        }
        push(node, l, r);
        int mid = (l + r) / 2;
        add(ql, qr, v, 2 * node, l, mid);
        add(ql, qr, v, 2 * node + 1, mid + 1, r);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    ll sum(int ql, int qr, int node, int l, int r) {
        if (qr < l || r < ql) {
            return 0;
        }
        if (ql <= l && r <= qr) {
            return tree[node];
        }
        push(node, l, r);
        int mid = (l + r) / 2;
        return sum(ql, qr, 2 * node, l, mid) + sum(ql, qr, 2 * node + 1, mid + 1, r);
    }

    void add(int l, int r, ll v) {
        add(l, r, v, 1, 0, n - 1);
    }

    ll sum(int l, int r) {
        return sum(l, r, 1, 0, n - 1);
    }
};

Ελέγχθηκε σε 500 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.