Segment tree
Bisemigroup model of line segment tree
(a little group theory stuff)
Visually, each node on the line segment tree has two kinds of information: data and mark, which are called\(D\)and\(T\)。
-
then need to exist\(D*D=D^\prime\)transfer, that is, data merging.
-
as well as\(D*T=D^\prime\), that is, mark transfer.
-
as well as\(T*T=T^{\prime}\), that is, mark merging.
At the same time, it is also necessary to satisfy the associative law and the distributive law. This is a semigroup, and there is an identity element.\(\epsilon\),make\(T*\epsilon=\epsilon*T=T\)It is a monoid group. Then we can maintain two structures and add three types of transfers.
Here's an example.
Interval addition, interval multiplication, and interval query. then there is\(D=\{l,s\}\) , \(T=\{a,b\}\) 。
then there is\((l_1,s_1)*(l_2,s_2)=(l_1+l_2,s_1+s_2)\)。
as well as\((l,s)*(a,b)=(l,as+lb)\)。
as well as\((a_1,b_1)*(a_2,b_2)=(a_1a_2,b_1a_2+b_2)\)。
Obviously, these things can be maintained using matrices.
Matrix multiplication and segment tree labeling
Interval addition segment tree
But this is not excellent. We are still stuck in the general mark and cannot extricate ourselves.
Consider maintaining a vector for each interval\(\vec{a}:\)
Our operation of adding a certain number to this interval can be regarded as left multiplication of a matrix:
At this point, we only need to maintain the left multiplication matrix.
This can explain why only one lazy mark is needed to maintain the interval plus information.
Considering that the left multiplication is an upper triangular matrix, it can be proved that the upper triangle is multiplied by the upper triangle or the upper triangle. In this scenario, only the position value of the upper right corner will change, so only one mark is needed to maintain the value of the upper right corner, that is But, it is the lazy mark that we usually maintain.
Segment tree historical version and
Assume only interval addition operations.
Each interval maintains a vector\(\vec{a}:\)
in\(his\)Represents the historical version sum,\(sum\)Represents the current interval sum,\(len\)is the interval length.
There is no change in the operation of interval addition by left-multiplying the matrix.
But we have more orders\(his\leftarrow his+sum\)For operations, consider using matrix representation:
Just maintain the left multiplication matrix.
Line segment tree historical maximum value
generalized matrix
two matrices\(A_{i, k}, B_{k, j}\)Multiply to get\(C_{i, j}\),satisfy\(C_{i, j}=\sum A_{i, k} B_{k, j}\) 。
When dealing with interval maximum values and historical maximum values, generalized moment multiplication is often used, that is\(C_{i, j}=\max \left(A_{i, k}+B_{k, j}\right)\) 。
Here, we only need to maintain,\(+ \max\)Two operations, they satisfy
- Commutative law:\(a+b=b+a, \max (a, b)=\max (b, a)\) 。
- Associative law:\((a+b)+c=a+(b+c), \max (\max (a, b), c)=\max (a, \max (b, c))\) 。
- Unit Yuan:\(a+0=0+a=a, \max (a,-\infty)=\max (-\infty, a)=a\) 。
- Additive inverse (opposite number):\(a+(-a)=(-a)+a=0\) 。
- Distributive law:\(a+\max (b, c)=\max (a+b, a+c), \max (a, b)+c=\max (a+c, b+c)\) 。
Generalized matrix multiplication is obviously associative.
The historical maximum value of the interval is maintained.
Consider maintaining a vector for each number in the sequence\(\left[\begin{array}{l}a_i \\ b_i\end{array}\right], ~ a_i\)represents the current value,\(b_i\)Represents the historical maximum value, and uses a line segment tree to maintain the interval vector sum (i.e.\(a_i, b_i\)the maximum value).
Then the interval plus\(k\)can be seen as\(\left[\begin{array}{l}a \\ b\end{array}\right] \leftarrow\left[\begin{array}{c}a+k \\ \max \{b, a+k\}\end{array}\right]\), generalized matrix multiplication can be easily constructed:\(\begin{bmatrix}
k & -\infty \\
k & 0
\end{bmatrix}
\begin{bmatrix}
a \\
b
\end{bmatrix}=\left[\begin{array}{c}a+k \\ \max \{b, a+k\}\end{array}\right]\), so the lazy mark can be set to\(\begin{bmatrix}
k & -\infty \\
k & 0
\end{bmatrix}\)this matrix.
example:P4314 CPU Monitoring - Luogu | New Ecosystem of Computer Science Education
This question needs to support interval assignment. (This operation can be converted into interval addition, that is, even if the line segment tree node is completely covered by the interval, as long as the maximum value is not equal to the minimum value, the recursion continues. According to the color segment equalization theory, the amortized time complexity of this part is\(O(n)\) ）。
You can add another dimension to the vector so that it becomes\(\left[\begin{array}{l}a \\ b \\ 0\end{array}\right]\), so there is\(\left[\begin{array}{ccc}
-\infty & -\infty & k \\
-\infty & 0 & k \\
-\infty & -\infty & 0
\end{array}\right]\left[\begin{array}{l}
a \\
b \\
0
\end{array}\right]=\left[\begin{array}{c}
k \\
\max \{b, k\} \\
0
\end{array}\right]\)。
Convert matrix to tokens
In ordinary historical maximum value maintenance, we can notice:
\(\begin{bmatrix}a&-\infty\\b&0\end{bmatrix}+\begin{bmatrix}c&-\infty\\d&0\end{bmatrix}=\begin{bmatrix}\max(a,c)&-\infty\\\max(b,d)&0\end{bmatrix}\\\begin{bmatrix}a&-\infty\\b&0\end{bmatrix}\begin{bmatrix}c&-\infty\\d&0\end{bmatrix}=\begin{bmatrix}a+c&-\infty\\\max(b+c,d)&0\end{bmatrix}\)
The value of the second column of the left multiplied matrix always remains unchanged, and only the value of the first column changes, so the value of the first column of the matrix can be maintained.
In fact, the two values in the first column of the left multiplication matrix correspond to the "addition and subtraction marks" and the "historical maximum addition and subtraction mark" in the paper respectively.
example:P6242 [Template] Line Segment Tree 3 (Interval Maximum Value Operation, Interval Historical Maximum Value) - Luogu | New Ecosystem of Computer Science Education
Let’s not consider the issue of historical maximum value for now.
Taking into account the interval\(\min\)The operation will only work on maximum values not exceeding\(k\)nodes have an impact, we can generate ideas in this regard. In order to get the complexity right, a node of the line segment tree must maintain three pieces of information: the maximum value of the interval\(mx\), the interval is strictly the second largest value\(se\)and the number of maximum values\(cnt\). Then, when an interval maximum operation is applied to this node, it can be divided into the following three situations:
- \(k\geq mx\), at this time, the operation will not affect the current node and exit directly;
-
\(se<k<mx\), at this time all the maximum values in the interval maintained by this node will be modified to\(k\), while the maximum number of values remains unchanged. Will
interval sum plus\(cnt\times (k-mx)\), mark it as lazy and then exit; - \(k\leq se\), At this time, the interval information cannot be updated quickly, so we need to continue to recurse into the left and right subtrees and merge the information during backtracking.
The proof of the original paper tells us that the complexity without modification operations is\(O(m\log n)\)of.
Due to interval addition and subtraction operations, the value range of some nodes will increase. The time complexity given in the paper is\(O(m\log^2n)\). In actual implementation, you will find that this upper bound is often unsatisfactory, and the speed is almost the same as the large constant.\(\log\)near.
At this point, return to the original question. We divide the value range of this problem into maximum value and non-maximum value, and maintain information and\(tag\)。
The matrix here can only simplify the historical maximum value change process of the maximum value and non-maximum value respectively. It cannot be maintained directly under the generalized matrix\(sum\), at the same time, the records of the second largest value and the largest number of values also need to be recorded separately. A better method for this question is to directly use\(tag\)Transfer (I will not completely use matrices to complete this question).
const int N = 5e5 + 5;
struct SGT {
ll sum;
int maxa, maxb, cnt, se;
int add1, add2, hadd1, hadd2; // The mark of the maximum value/non-maximum value The historical maximum mark of the maximum value/non-maximum value
} tr[N << 2];
#define ls (id << 1)
#define rs (id << 1 | 1)
#define mid (l + r >> 1)
il void pushup(int id) {
tr[id].sum = tr[ls].sum + tr[rs].sum;
tr[id].maxa = max(tr[ls].maxa, tr[rs].maxa);
tr[id].maxb = max(tr[ls].maxb, tr[rs].maxb);
if (tr[ls].maxa == tr[rs].maxa) {
tr[id].se = max(tr[ls].se, tr[rs].se);
tr[id].cnt = tr[ls].cnt + tr[rs].cnt;
} else if (tr[ls].maxa > tr[rs].maxa) {
tr[id].se = max(tr[ls].se, tr[rs].maxa);
tr[id].cnt = tr[ls].cnt;
} else {
tr[id].se = max(tr[ls].maxa, tr[rs].se);
tr[id].cnt = tr[rs].cnt;
}
}
void build(int l, int r, int id) {
if (l == r) {
int x; read(x); tr[id].add1 = tr[id].add2 = tr[id].hadd1 = tr[id].hadd2 = 0;
return tr[id].sum = tr[id].maxa = tr[id].maxb = x, tr[id].se = -2e9, tr[id].cnt = 1, void();
}
build(l, mid, ls), build(mid + 1, r, rs);
pushup(id);
}
il void work(int tag1, int tag2, int htag1, int htag2, int l, int r, int id) {
tr[id].sum += 1ll * tag1 * tr[id].cnt + 1ll * tag2 * (r - l + 1 - tr[id].cnt);
tr[id].maxb = max(tr[id].maxb, tr[id].maxa + htag1); tr[id].maxa += tag1;
if (tr[id].se != -2e9) tr[id].se += tag2;
tr[id].hadd1 = max(tr[id].hadd1, tr[id].add1 + htag1);
tr[id].hadd2 = max(tr[id].hadd2, tr[id].add2 + htag2);
tr[id].add1 += tag1, tr[id].add2 += tag2;
}
il void pushdown(int l, int r, int id) {
int mx = max(tr[ls].maxa, tr[rs].maxa);
if (tr[ls].maxa == mx) work(tr[id].add1, tr[id].add2, tr[id].hadd1, tr[id].hadd2, l, mid, ls);
else work(tr[id].add2, tr[id].add2, tr[id].hadd2, tr[id].hadd2, l, mid, ls);
if (tr[rs].maxa == mx) work(tr[id].add1, tr[id].add2, tr[id].hadd1, tr[id].hadd2, mid + 1, r, rs) ;
else work(tr[id].add2, tr[id].add2, tr[id].hadd2, tr[id].hadd2, mid + 1, r, rs);
tr[id].add1 = tr[id].add2 = tr[id].hadd1 = tr[id].hadd2 = 0;
}
il void add(int l, int r, int x, int y, int k, int id) {
if (l > y || r < x) return ;
if (l >= x && r <= y) {
tr[id].sum += 1LL * k * (r - l + 1);
tr[id].maxa += k; tr[id].maxb = max(tr[id].maxb, tr[id].maxa);
if (tr[id].se != -2e9) tr[id].se += k;
tr[id].add1 += k, tr[id].add2 += k;
tr[id].hadd1 = max(tr[id].hadd1, tr[id].add1);
tr[id].hadd2 = max(tr[id].hadd1, tr[id].add2);
return ;
}
pushdown(l, r, id);
add(l, mid, x, y, k, ls), add(mid + 1, r, x, y, k, rs);
pushup(id);
}
il void mdf(int l, int r, int x, int y, int k, int id) {
if (l > y || r < x || tr[id].maxa <= k) return ;
if (l >= x && r <= y && tr[id].se < k) {
int t = tr[id].maxa - k;
tr[id].sum -= 1LL * tr[id].cnt * t;
tr[id].maxa = k, tr[id].add1 -= t;
return ;
}
pushdown(l, r, id);
mdf(l, mid, x, y, k, ls), mdf(mid + 1, r, x, y, k, rs);
pushup(id);
}
il ll qry_sum(int l, int r, int x, int y, int id) {
if (l > y || r < x) return 0;
if (l >= x && r <= y) return tr[id].sum;
pushdown(l, r, id);
return qry_sum(l, mid, x, y, ls) + qry_sum(mid + 1, r, x, y, rs);
}
il ll qry_a(int l, int r, int x, int y, int id) {
if (l > y || r < x) return -2e9;
if (l >= x && r <= y) return tr[id].maxa;
pushdown(l, r, id);
return max(qry_a(l, mid, x, y, ls), qry_a(mid + 1, r, x, y, rs));
}
il ll qry_b(int l, int r, int x, int y, int id) {
if (l > y || r < x) return -2e9;
if (l >= x && r <= y) return tr[id].maxb;
pushdown(l, r, id);
return max(qry_b(l, mid, x, y, ls), qry_b(mid + 1, r, x, y, rs));
}
int n, m;
signed main() {
read(n, m);
build(1, n, 1);
while (m--) {
int op, l, r, k;
read(op, l, r);
if (op == 1) read(k), add(1, n, l, r, k, 1);
else if (op == 2) read(k), mdf(1, n, l, r, k, 1);
else if (op == 3) write(qry_sum(1, n, l, r, 1)), ptc('\n');
else if (op == 4) write(qry_a(1, n, l, r, 1)), ptc('\n');
else if (op == 5) write(qry_b(1, n, l, r, 1)), ptc('\n');
}
return 0;
}I always think that looking at the code is the best way to understand this kind of question.
Ordinary matrix multiplication and interval history sum
example:P8868[NOIP2022] Contest
We offline all queries, on the right endpoint\(r\)Make a scan line.
During the scanning process, we set\(X_l\)and\(Y_l\)Respectively\(l,\ldots,r\)within range\(A_i\)and\(B_i\)the maximum value.
We can scan each\(l\),maintain
In this case, what we want to query is\(l\sim r\)interval\(S\)and.
And our operation is the interval\(X\)modify (overwrite),interval\(Y\)modify (overwrite), and\(S\leftarrow S+X\times Y\)。
At this point, this question turns to interval coverage, interval history and issues.
Maintenance vector:
in\(his\)Represents the historical version sum,\(ab\)express\((\sum A_i)\times(\sum B_i)\), \(a,b\)Respectively\(\sum A_i,\sum B_i\)。
So, for\(A\)The interval addition operation can be expressed as:
right\(B\)The operation is the same.
The operation of refreshing the historical sum can be expressed as:
Just maintain the left multiplication matrix. complexity\(O(k^3n\log n)\), can be obtained\(76\)point. Full marks may be obtained after card constant and multiplication expansion.
Optimize marker constants
As mentioned earlier, there is always a lot of information in the matrix that remains unchanged, so this information theory does not need to be recorded.
Let's take the following multiplication as an example:
There are two types of matrices to operate on:
This means that we only need to pay attention to the form:
This means that we only need to maintain the three positions in the upper right corner, and modify them directly according to the above formula each time. In this way, the constants are greatly reduced, which is consistent with the constants for maintaining a bunch of tags.
However, I found that there is actually a value in the upper right corner, so I revised it again:
This means that we only need to maintain the three positions in the upper right corner and modify them directly according to the above formula each time, so that the constants are greatly reduced.
In the same way, forP8868[NOIP2022] Contest, the only useful locations found are\(9\), maintain this\(9\)location is enough.
If it is difficult to observe, you might as well assign random values to the matrix and print out the unchanged positions.
Some tips on vector construction
Generally speaking, the vector we need to construct should be in the form of an upper/lower triangular matrix for each operation, which makes it easier for us to observe, understand, and optimize.
And if it is to become an upper triangle, it means that for\(\vec{a}_i\)only by\(j>i,\vec{a}_j\)transferred.
So generally speaking, the constant length will be placed at the bottom, historical version information will be placed at the top, and general information will be placed in the middle.
Conclusion
Most of this article is transcribed from high-quality blogs.
A brief discussion on the techniques of maintaining line segment tree markers through matrix multiplication - Luogu Column
Algorithm Study Notes (34): Matrix Multiplication and Line Segment Tree Marking - jeefy - Blog Park
Interval history operations, from matrix multiplication to labeling - Luogu column
Line Segment Tree Advanced Notes - oXUo - Blog Park
[NOIP 2022] T4 Competition Problem Solutions