Core Logic and Mathematical Principles
When a segment tree needs to maintain multiple interval modification operations simultaneously (such as both multiplication and addition modifications in the same interval) or maintain nonlinear information (such as the sum of squares in an interval), the core difficulty lies in defining the algebraic priority of multiple tags and the algebraic expansion of nonlinear states.
1. Algebraic Maintenance of Mixed Interval Multiplication and Addition
Assuming the current node maintains an interval sum of $S$, and this node has been subjected to operations of multiplying by a number $m$ and adding a number $a$. To represent the state at any moment with a unified algebraic expression, we define the composite transformation as:
$$S_{new} = S \times m + a \times len$$
where $len$ is the current interval length.
If at this time the interval receives another multiplication operation (multiplying by $M$) and an addition operation (adding $A$), based on the associative and distributive laws, the new state is:
$$S_{final} = (S \times m + a \times len) \times M + A \times len = S \times (m \times M) + (a \times M + A) \times len$$
From this, we derive the hardcore rule for merging multiple tags:
- New Multiplication Tag: $m' = m \times M$
- New Addition Tag: $a' = a \times M + A$
Conclusion: The multiplication tag directly alters the existing addition tag, while the addition tag does not affect the existing multiplication tag. Therefore, the priority of the multiplication tag is higher than that of the addition tag. When passing down tags, multiplication must be handled first, followed by addition.
2. Algebraic Expansion of the Sum of Squares in Intervals
When the segment tree maintains the sum of squares $\\sum X_i^2$, if an operation adds $v$ to the interval, each element $X_i \leftarrow X_i + v$. Using the complete square formula:
$$\sum (X_i + v)^2 = \sum (X_i^2 + 2vX_i + v^2) = \sum X_i^2 + 2v \sum X_i + v^2 \sum 1$$
The state transition equation becomes:
$$S_{sq\text{new}} = S_{sq} + 2v \times S_{sum} + v^2 \times len$$
This means that to maintain the sum of squares in an interval, the first-order sum ($S_{sum}$) must also be maintained.
State Design and Algorithm Derivation
1. State of the Mixed Multiplication and Addition Segment Tree
Each node maintains three values: sum (interval sum), mul (multiplication lazy tag, initialized to $1$), add (addition lazy tag, initialized to $0$).
Tag Passing Down (Pushdown) Derivation
For the left child node $ls$ of node $u$ ($ls = u \ll 1$):
- Update the child node's data value (must strictly follow the order of multiplication first, then addition):
$$sum[ls] = (sum[ls] \times mul[u] + add[u] \times len_{ls}) \pmod P$$
- Update the child node's tag values:
$$mul[ls] = (mul[ls] \times mul[u]) \pmod P$$
$$add[ls] = (add[ls] \times mul[u] + add[u]) \pmod P$$
- The same applies to the right child node. After passing down, restore the physical baseline state:
mul[u] = 1, add[u] = 0.
2. State of the Segment Tree for the Sum of Squares in Intervals
Each node maintains: sum1 (first-order sum $\\sum X_i$), sum2 (second-order sum of squares $\\sum X_i^2$), lazy (addition tag).
Tag Passing Down (Pushdown) Derivation
For child node $ls$, if the parent node has an addition tag $v$:
- First, update the second-order sum based on the first-order sum: $sum2[ls] = sum2[ls] + 2 \times v \times sum1[ls] + v \times v \times len_{ls}$
- Then update the first-order sum: $sum1[ls] = sum1[ls] + v \times len_{ls}$
- Accumulate the lazy tag: $lazy[ls] = lazy[ls] + v$
C++ Standard Source Code (NOIP Style: Taking Interval Multiplication + Addition as an Example)
#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 sum[MAXN << 2];
long long mul[MAXN << 2];
long long add[MAXN << 2];
long long a[MAXN];
long long MOD; // NOIP mixed common large prime modulus
inline void pushup(int u) {
sum[u] = (sum[u << 1] + sum[u << 1 | 1]) % MOD;
}
// Core mixed pushdown
inline void pushdown(int u, int l, int r) {
int m = (l + r) >> 1;
int ls = u << 1, rs = u << 1 | 1;
// 1. Handle the left subtree
sum[ls] = (sum[ls] * mul[u] % MOD + add[u] * (m - l + 1) % MOD) % MOD;
mul[ls] = (mul[ls] * mul[u]) % MOD;
add[ls] = (add[ls] * mul[u] % MOD + add[u]) % MOD; // Critical pitfall: the original addition tag of the child node must first be multiplied by the multiplication tag of the parent node
// 2. Handle the right subtree
sum[rs] = (sum[rs] * mul[u] % MOD + add[u] * (r - m) % MOD) % MOD;
mul[rs] = (mul[rs] * mul[u]) % MOD;
add[rs] = (add[rs] * mul[u] % MOD + add[u]) % MOD;
// 3. Reset the current node's tags
mul[u] = 1;
add[u] = 0;
}
void build(int u, int l, int r) {
mul[u] = 1; // Critical pitfall: the multiplication tag must be initialized to 1; mistakenly initializing to 0 will cause the entire tree's data to be erased
add[u] = 0;
if (l == r) {
sum[u] = a[l] % MOD;
return;
}
int m = (l + r) >> 1;
build(u << 1, l, m);
build(u << 1 | 1, m + 1, r);
pushup(u);
}
void update_mul(int u, int l, int r, int ql, int qr, long long v) {
if (ql <= l && r <= qr) {
sum[u] = (sum[u] * v) % MOD;
mul[u] = (mul[u] * v) % MOD;
add[u] = (add[u] * v) % MOD; // The multiplication operation directly affects the current node's addition tag
return;
}
pushdown(u, l, r);
int m = (l + r) >> 1;
if (ql <= m) update_mul(u << 1, l, m, ql, qr, v);
if (qr > m) update_mul(u << 1 | 1, m + 1, r, ql, qr, v);
pushup(u);
}
void update_add(int u, int l, int r, int ql, int qr, long long v) {
if (ql <= l && r <= qr) {
sum[u] = (sum[u] + v * (r - l + 1) % MOD) % MOD;
add[u] = (add[u] + v) % MOD; // The addition operation does not affect the current node's multiplication tag
return;
}
pushdown(u, l, r);
int m = (l + r) >> 1;
if (ql <= m) update_add(u << 1, l, m, ql, qr, v);
if (qr > m) update_add(u << 1 | 1, m + 1, r, ql, qr, v);
pushup(u);
}
long long query(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return sum[u];
pushdown(u, l, r);
int m = (l + r) >> 1;
long long res = 0;
if (ql <= m) res = (res + query(u << 1, l, m, ql, qr)) % MOD;
if (qr > m) res = (res + query(u << 1 | 1, m + 1, r, ql, qr)) % MOD;
return res;
}
int main() {
int n = read(), m = read();
MOD = 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 v = read();
update_mul(1, 1, n, ql, qr, v);
} else if (opt == 2) {
int ql = read(), qr = read();
long long v = read();
update_add(1, 1, n, ql, qr, v);
} else {
int ql = read(), qr = read();
printf("%lld\n", query(1, 1, n, ql, qr));
}
}
return 0;
}
NOIP Practical Avoidance Guide
1. Incorrect Initialization of Multiplication Tags
In a multi-tag segment tree, contestants often habitually clear all arrays during build or declaration. If the multiplication tag mul[] is mistakenly initialized to 0, executing pushdown will cause all subtree nodes' data to become 0. It is essential to explicitly assign all nodes' mul[u] a value of 1 during tree construction.
2. Non-atomicity of Modulus During Tag Passing Down
When executing add[ls] = (add[ls] * mul[u] + add[u]) % MOD;, multiplication and addition are intertwined. A common low-level error is to omit the modulus in the intermediate steps, leading to add[ls] * mul[u] overflowing long long (which can reach up to $(10^9) \times (10^9) = 10^{18}$; if two large numbers are multiplied without modulus consecutively, it will truncate directly). Each stage's multiplication and addition results must be immediately wrapped in % MOD.
3. Reversed Update Order in Square Sum Maintenance
In the pushdown of the segment tree maintaining the sum of squares in intervals, it is necessary to first update the square sum sum2, then update the first-order sum sum1. This is because the update formula for sum2 includes sum1 (i.e., $2v \times sum1$). If sum1 is first incremented by $v \times len$, then the current sum1 is already in a future state, substituting it into the calculation formula for sum2 will lead to double counting, causing the mathematical logic to collapse completely.
Classic NOIP/Luogu Problems
1. Luogu P3373 [Template] Segment Tree 2
- Problem Description: Given a sequence of numbers, you need to perform the following three operations: multiply each number in a certain interval by $x$; add $x$ to each number in a certain interval; query the sum of each number in a certain interval modulo $P$.
- Essential Nature of the Problem: Standard industrial-grade benchmark for dual-tag segment trees.
- Core Problem-Solving Idea: As described above, the core lies in strictly adhering to the state definition of $S \times mul + add$ during
pushdown. When encountering an interval multiplication modification $v$, allsum,mul, andaddof the current node are multiplied by $v$; when encountering an interval addition modification $v$, onlysumis incremented by $v \times len$, andaddis incremented by $v$. The conflicts of tags are resolved through rigid regulations of operator priority.
2. Luogu P1471 Rectangle Variance / Luogu P6327 Interval Sine Sum (Variant Extension)
- Problem Description: Maintain a sequence that supports adding a real number $x$ to an interval and querying the variance of that interval in real-time.
- Essential Nature of the Problem: Maintenance of nonlinear high-order information in intervals.
- Core Problem-Solving Idea: The variance formula is $D = \frac{1}{n}\sum X_i^2 - \bar{X}^2$. Therefore, the essence of the problem is equivalent to requiring the segment tree to efficiently maintain both the "first-order sum $\\sum X_i$" and the "sum of squares $\\sum X_i^2$" in the interval. By using the complete square formula to expand, the change in the first-order sum can be used to drive the increment of the second-order sum of squares in real-time, with a single modification complexity of $O(\log N)$.