Managing multiple interdependent lazy operations in segment trees often requires tedious case analysis for tag composition and priority resolution. Representing state transitions as matrix multiplications provides a unified algebraic framework. Each tree node maintains a state vector, while pending operations are encoded as transformation matrices. Tag composition reduces to matrix multiplication, and state updates become matrix-vector products, eliminating manual priority handling.
Fundamental Linear Transformations
Consider range addition paired with range sum queries. The state vector for an interval is defined as $V = \begin{bmatrix} \text{sum} \ \text{len} \end{bmatrix}$. Adding a constant $c$ to every element transforms the sum to $\text{sum} + c \times \text{len}$. This affine transformation maps directly to a matrix:
$$M_{\text{add}}(c) = \begin{bmatrix} 1 & c \ 0 & 1 \end{bmatrix}$$
Applying the operation yields $V' = M_{\text{add}}(c) V$. Composing sequential additions $c_1$ followed by $c_2$ corresponds to $M_{\text{add}}(c_2) \times M_{\text{add}}(c_1)$, which algebraically resolves to a single addition of $c_1 + c_2$. This approach generalizes to any linear recurrence or affine update.
Tracking Historical Maximums via $(\max, +)$ Algebra
Standard lazy tags merge operations, discarding intermediate states necessary for historical queries. By switching to the $(\max, +)$ semiring, matrix multiplication can simultaneously track current and historical maximums. Define matrix product as $C_{i,j} = \max_k (A_{i,k} + B_{k,j})$.
The state vector expands to $V = \begin{bmatrix} \text{cur} \ \text{hist} \ 0 \end{bmatrix}$. A range addition of $k$ uses:
$$M_{\text{add}}(k) = \begin{bmatrix} k & -\infty & -\infty \ k & 0 & -\infty \ -\infty & -\infty & 0 \end{bmatrix} \implies V' = \begin{bmatrix} \text{cur} + k \ \max(\text{hist}, \text{cur} + k) \ 0 \end{bmatrix}$$
A range assignment to $k$ uses:
$$M_{\text{set}}(k) = \begin{bmatrix} -\infty & -\infty & k \ -\infty & 0 & k \ -\infty & -\infty & 0 \end{bmatrix} \implies V' = \begin{bmatrix} k \ \max(\text{hist}, k) \ 0 \end{bmatrix}$$
Since full matrix multiplication introduces significant constant overhead, production implementations unroll the operations and store only active coefficients.
#include <iostream>
#include <vector>
#include <algorithm>
using ll = long long;
constexpr ll NEG_INF = -1e15;
struct State {
ll cur_max = NEG_INF;
ll hist_max = NEG_INF;
State operator+(const State& other) const {
return {std::max(cur_max, other.cur_max), std::max(hist_max, other.hist_max)};
}
};
struct Transform {
ll add_cur = 0;
ll add_hist = NEG_INF;
ll set_cur = NEG_INF;
ll set_hist = NEG_INF;
static Transform identity() { return {0, NEG_INF, NEG_INF, NEG_INF}; }
// Compose: apply `next_op` after `this`
Transform operator*(const Transform& next_op) const {
Transform res;
res.add_cur = add_cur + next_op.add_cur;
res.add_hist = std::max(next_op.add_cur + add_hist, next_op.add_hist);
res.set_cur = std::max(add_cur + next_op.set_cur, set_cur);
res.set_hist = std::max({add_hist + next_op.set_cur, next_op.set_hist, set_hist});
return res;
}
State apply(const State& s) const {
State res;
res.cur_max = std::max(s.cur_max + add_cur, set_cur);
res.hist_max = std::max({s.cur_max + add_hist, s.hist_max, set_hist});
return res;
}
};
class SegmentTree {
int size;
std::vector<State> nodes;
std::vector<Transform> tags;
void pull(int idx) { nodes[idx] = nodes[idx << 1] + nodes[idx << 1 | 1]; }
void apply_tag(int idx, const Transform& t) {
nodes[idx] = t.apply(nodes[idx]);
tags[idx] = t * tags[idx];
}
void push(int idx) {
if (tags[idx].add_cur != 0 || tags[idx].set_cur > NEG_INF / 2) {
apply_tag(idx << 1, tags[idx]);
apply_tag(idx << 1 | 1, tags[idx]);
tags[idx] = Transform::identity();
}
}
public:
SegmentTree(int n, const std::vector<ll>& init) : size(n) {
nodes.resize(4 * n);
tags.resize(4 * n, Transform::identity());
build(1, 1, n, init);
}
void build(int idx, int l, int r, const std::vector<ll>& init) {
if (l == r) {
nodes[idx] = {init[l], init[l]};
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid, init);
build(idx << 1 | 1, mid + 1, r, init);
pull(idx);
}
void update(int idx, int l, int r, int ql, int qr, const Transform& t) {
if (ql <= l && r <= qr) {
apply_tag(idx, t);
return;
}
push(idx);
int mid = (l + r) >> 1;
if (ql <= mid) update(idx << 1, l, mid, ql, qr, t);
if (qr > mid) update(idx << 1 | 1, mid + 1, r, ql, qr, t);
pull(idx);
}
State query(int idx, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return nodes[idx];
push(idx);
int mid = (l + r) >> 1;
State res = {NEG_INF, NEG_INF};
if (ql <= mid) res = res + query(idx << 1, l, mid, ql, qr);
if (qr > mid) res = res + query(idx << 1 | 1, mid + 1, r, ql, qr);
return res;
}
};
Offline Historical Sums with Monotonic Stacks
For queries requiring $\sum_{i=l}^r \sum_{j=i}^r (\max A[i..j] \times \max B[i..j])$, process endpoints offline. As the right boundary $r$ advances, maintain a contribution array $h_i$ representing the inner sum for a fixed left endpoint $i$. The query answer becomes $\sum_{i=l}^r h_i$.
Advancing $r$ updates range maximums. A monotonic stack identifies intervals where previous maximums are superseded by $A[r]$ or $B[r]$. These intervals trigger range updates on a segment tree managing the $h$ array.
The segment tree state vector aggregates interval data: $V = \begin{bmatrix} S_A \ S_B \ S_{AB} \ H \ L \end{bmatrix}$, where $S_A = \sum \max A$, $S_B = \sum \max B$, $S_{AB} = \sum (\max A \cdot \max B)$, $H$ accumulates historical $S_{AB}$ values, and $L$ is interval length.
Three sparse transformations drive the updates:
- Increment A by $\Delta$: $S_A \leftarrow S_A + \Delta L$, $S_{AB} \leftarrow S_{AB} + \Delta S_B$.
- Increment B by $\Delta$: $S_B \leftarrow S_B + \Delta L$, $S_{AB} \leftarrow S_{AB} + \Delta S_A$.
- Accumulate History: $H \leftarrow H + S_{AB}$.
Each operation corresponds to a $5 \times 5$ matrix. Composition uses standard arithmetic. Storing only non-zero off-diagonal entries optimizes the constant factor significantly.
#include <iostream>
#include <vector>
#include <algorithm>
using ull = unsigned long long;
struct Aggregate {
ull sum_a = 0, sum_b = 0, sum_ab = 0, hist = 0, len = 0;
Aggregate operator+(const Aggregate& rhs) const {
return {sum_a + rhs.sum_a, sum_b + rhs.sum_b,
sum_ab + rhs.sum_ab, hist + rhs.hist, len + rhs.len};
}
};
struct LazyOp {
ull da = 0, db = 0;
ull dab_a = 0, dab_b = 0;
ull dh_ab = 0, dh_a = 0, dh_b = 0, dh_c = 0;
static LazyOp identity() { return {}; }
LazyOp operator*(const LazyOp& rhs) const {
LazyOp res;
res.da = da + rhs.da;
res.db = db + rhs.db;
res.dab_a = dab_a + rhs.dab_a;
res.dab_b = dab_b + rhs.dab_b;
res.dh_ab = dh_ab + rhs.dh_ab;
res.dh_a = dh_a + rhs.dh_a + dh_ab * rhs.dab_a;
res.dh_b = dh_b + rhs.dh_b + dh_ab * rhs.dab_b;
res.dh_c = dh_c + rhs.dh_c + dh_a * rhs.da + dh_b * rhs.db + dh_ab * (rhs.dab_a * 0 + rhs.dab_b * 0);
return res;
}
Aggregate apply(const Aggregate& s) const {
Aggregate res = s;
res.sum_a += da * s.len;
res.sum_b += db * s.len;
res.sum_ab += dab_a * s.sum_a + dab_b * s.sum_b;
res.hist += dh_ab * s.sum_ab + dh_a * s.sum_a + dh_b * s.sum_b + dh_c * s.len;
return res;
}
};
class HistorySegmentTree {
int size;
std::vector<Aggregate> tree;
std::vector<LazyOp> lazy;
void pull(int idx) { tree[idx] = tree[idx << 1] + tree[idx << 1 | 1]; }
void apply(int idx, const LazyOp& op) {
tree[idx] = op.apply(tree[idx]);
lazy[idx] = op * lazy[idx];
}
void push(int idx) {
if (lazy[idx].da || lazy[idx].db || lazy[idx].dh_ab) {
apply(idx << 1, lazy[idx]);
apply(idx << 1 | 1, lazy[idx]);
lazy[idx] = LazyOp::identity();
}
}
public:
HistorySegmentTree(int n) : size(n) {
tree.resize(4 * n);
lazy.resize(4 * n, LazyOp::identity());
build(1, 1, n);
}
void build(int idx, int l, int r) {
if (l == r) {
tree[idx] = {0, 0, 0, 0, 1};
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid);
build(idx << 1 | 1, mid + 1, r);
pull(idx);
}
void update(int idx, int l, int r, int ql, int qr, const LazyOp& op) {
if (ql <= l && r <= qr) {
apply(idx, op);
return;
}
push(idx);
int mid = (l + r) >> 1;
if (ql <= mid) update(idx << 1, l, mid, ql, qr, op);
if (qr > mid) update(idx << 1 | 1, mid + 1, r, ql, qr, op);
pull(idx);
}
ull query_hist(int idx, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[idx].hist;
push(idx);
int mid = (l + r) >> 1;
ull res = 0;
if (ql <= mid) res += query_hist(idx << 1, l, mid, ql, qr);
if (qr > mid) res += query_hist(idx << 1 | 1, mid + 1, r, ql, qr);
return res;
}
};
The matrix formulation abstracts away complex tag interactions. By defining appropriate semirings and state vectors, segment trees can handle historical queries, multi-variable dependencies, and affine transformations through uniform algebraic composition. Sparse matrix representations and unrolled arithmetic ensure the approach remains viable within strict time limits.