NeFut Logo NeFut
中 Admin Login

Efficient Interval Updates and Queries: Implementation and Application of Lazy Segment Trees

Published at: 2026-05-27 09:17 Last updated: 2026-06-06 13:04
#C++ #Tutorial

Core Logic and Mathematical Principles

When maintaining interval modifications (such as interval addition and assignment), if we use a brute-force approach to update each leaf node in the interval one by one, the time complexity of a single operation will degrade to $O(N \log N)$. To ensure the algorithm completes in $O(\log N)$ logarithmic complexity, we introduce the Lazy Tag mechanism.

Lazy Update Principle

The core idea of lazy tagging is to "update only when necessary, and propagate down when passing through". When an interval modification operation completely covers the closed interval $[L, R]$ represented by a node, we update the data of that node and mark it with a lazy tag $tag$, without further recursion into its subtree. This tag indicates: "The data in the subtree of this node is outdated, and the correct modification increment is temporarily held at the current node".

Maintaining Mathematical Correctness

Assume the sum of the current interval $[L, R]$ is $sum$, and it has been marked with an addition lazy tag $v$.

$$sum = sum + (R - L + 1) \times v$$

State Design and Algorithm Derivation

1. State Definition

Each segment tree node, in addition to maintaining the interval sum tree[u], has an additional tag array lazy[u], which is initially all $0$.

2. Tag Propagation (Pushdown) Logic

Define the function pushdown(u, l, r). Let $m = (l + r) \gg 1$:

$$lazy[u \ll 1] = lazy[u \ll 1] + lazy[u]$$

$$lazy[u \ll 1 | 1] = lazy[u \ll 1 | 1] + lazy[u]$$

$$tree[u \ll 1] = tree[u \ll 1] + lazy[u] \times (m - l + 1)$$

$$tree[u \ll 1 | 1] = tree[u \ll 1 | 1] + lazy[u] \times (r - m)$$

3. Interval Modification (Update) Logic

Define the recursive function update(u, l, r, ql, qr, val):

  1. If $[l, r] \subseteq [ql, qr]$, the current interval is fully contained. Directly update the current node value, add the lazy tag, and terminate recursion:

$$tree[u] = tree[u] + (r - l + 1) \times val$$

$$lazy[u] = lazy[u] + val$$

  1. If not fully contained, it indicates that the tag must be propagated. First, perform pushdown(u, l, r).
  2. Let $m = (l + r) \gg 1$.
  1. After the subtree recursion ends, call pushup(u) to upload the latest correct child node information.

C++ Standard Source Code (NOIP Style)

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

using namespace std;

inline long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

const int MAXN = 100005;
long long tree[MAXN << 2];
long long lazy[MAXN << 2]; // Critical pitfall: the lazy array must open 4 times the space as the tree array
long long a[MAXN];

inline void pushup(int u) {
    tree[u] = tree[u << 1] + tree[u << 1 | 1];
}

// Core pushdown function
inline void pushdown(int u, int l, int r) {
    if (lazy[u]) {
        int m = (l + r) >> 1;

        // Propagate to left subtree
        lazy[u << 1] += lazy[u];
        tree[u << 1] += lazy[u] * (m - l + 1); // Must multiply by the actual interval length of the left subtree

        // Propagate to right subtree
        lazy[u << 1 | 1] += lazy[u];
        tree[u << 1 | 1] += lazy[u] * (r - m); // Must multiply by the actual interval length of the right subtree

        lazy[u] = 0; // Critical pitfall: must clear the physical tag of the current node after propagation
    }
}

void build(int u, int l, int r) {
    lazy[u] = 0;
    if (l == r) {
        tree[u] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(u << 1, l, m);
    build(u << 1 | 1, m + 1, r);
    pushup(u);
}

void update(int u, int l, int r, int ql, int qr, long long val) {
    if (ql <= l && r <= qr) {
        tree[u] += val * (r - l + 1);
        lazy[u] += val; // When fully covered, mark and return, do not continue recursion
        return;
    }
    pushdown(u, l, r); // If not fully covered, must propagate the old tag before recursive descent into the subtree
    int m = (l + r) >> 1;
    if (ql <= m) update(u << 1, l, m, ql, qr, val);
    if (qr > m) update(u << 1 | 1, m + 1, r, ql, qr, val);
    pushup(u); // After subtree modification is complete, update the current node with the latest state
}

long long query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return tree[u];
    }
    pushdown(u, l, r); // When querying, if we need to access the subtree, we must propagate the tag, otherwise we will read outdated data
    int m = (l + r) >> 1;
    long long res = 0;
    if (ql <= m) res += query(u << 1, l, m, ql, qr);
    if (qr > m) res += query(u << 1 | 1, m + 1, r, ql, qr);
    return res;
}

int main() {
    int n = read();
    int m = read();
    for (int i = 1; i <= n; ++i) a[i] = read();

    build(1, 1, n);

    while (m--) {
        int opt = read();
        if (opt == 1) {
            int ql = read(), qr = read();
            long long val = read();
            update(1, 1, n, ql, qr, val);
        } else {
            int ql = read(), qr = read();
            printf("%lld\n", query(1, 1, n, ql, qr));
        }
    }
    return 0;
}

NOIP Practical Pitfall Guide

1. Forgetting to call pushdown during query operations

Many contestants mistakenly believe that only update operations (update) need to handle tags. When executing the query function, if pushdown(u, l, r) is not called before splitting into the subtree, the outdated data stored in the subtree will be directly added as the answer, leading to a complete logical breakdown. Remember: as long as there is downward recursion in the code (i.e., ql <= m or qr > m branches), the previous line must forcibly execute pushdown.

2. Infinite accumulation caused by un-cleared tags

At the end of the pushdown logic, it is crucial to include lazy[u] = 0;. If this line is omitted, the next time the node triggers pushdown, the already propagated tags will be incorrectly added to the child nodes, causing data to increase linearly or even exponentially.

3. Leaf node triggering pushdown causing out-of-bounds

Although in the standard update and query logic, when $ql <= l && r <= qr$, it has already returned, leaf nodes ($l = r$) theoretically will not enter the branches that require tag propagation. However, in more complex variants of segment trees (such as dynamic opening points or binary search on trees), if pushdown is forcibly called in the case of $l = r$, accessing u << 1 will cause the array index to exceed MAXN << 2, triggering RE. When writing defensive code, you can add if (l == r) return; at the beginning of pushdown.

Classic NOIP/Luogu Problems

1. Luogu P3372 [Template] Segment Tree 1

2. Luogu P1253 [EGOI2021] Rearrangement / The Problem of Fusu

Original Source: local://6.2
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS