將線段樹封裝成模板
本文參考了ac-library。
定義：
設
是一個集合，
是某二元運算。
設
是一些
的一元運算的集合。
線段樹需要滿足的性質：
運算
滿足結合律。
存在單位元
，即
現有陣列
， 我們希望用線段樹維護以下操作：
區間修改。給定
和變換函式
，將區間內所有的元素進行變換，即
![\forall i\in[l,r],a_i\leftarrow f(a_i)](https://img.heatask.com/upload/website_attach/osgE6tumoT7FXAo18pC5IsZAI97y29jfrfsEJ+4CFEzzYhluT_lDJDrU6pj4IzgEZl5OrZfQVj_-zA9uT_y_3d_U+9RgiisPnfxE+I9-VEV3xVcB-qvMIXZSQP3zU.jpeg)
區間和查詢。給定
，返回
。
線段樹I 單點修改+區間查詢
線段樹
上圖是一棵線段樹，每一個結點
![[l,r]](https://img.heatask.com/upload/website_attach/UpPZYYpeUM6bVmA1zkE+wqt+kZIfK9jvkR5ZWEn0rcyKWuVu9uX0ag_nYGzXOv0+F.jpeg)
維護了
。
記
區間查詢
假設我們需要查詢
，只需要在樹中找到
，
的值。由於
運算滿足
結合律
，按照順序作
即可。
單點修改
假設我們需要修改
，修改區間
後，只要不斷 pushup，更新
；
；
；
。
兩種操作的時間複雜度均為
程式碼：
template
<
typename
T
，
auto
op
，
auto
e
>
class
segtree
{
int
n
=
0
；
vector
<
T
>
v
；
void
pushup
（
int
k
）
{
v
［
k
］
=
op
（
v
［
k
*
2
］，
v
［
k
*
2
+
1
］）；
}
void
set
（
int
now
，
int
k
，
int
l
，
int
r
，
T
x
）
{
if
（
l
>
k
||
r
<
k
）
return
；
if
（
l
==
k
&&
r
==
k
）
{
v
［
now
］
=
x
；
return
；
}
set
（
now
*
2
，
k
，
l
，
（
l
+
r
）
/
2
，
x
）；
set
（
now
*
2
+
1
，
k
，
（
l
+
r
）
/
2
+
1
，
r
，
x
）；
pushup
（
now
）；
}
T
query
（
int
now
，
int
ql
，
int
qr
，
int
l
，
int
r
）
{
if
（
l
>
qr
||
r
<
ql
）
return
e
（）；
if
（
l
>=
ql
&&
r
<=
qr
）
return
v
［
now
］；
return
op
（
query
（
now
*
2
，
ql
，
qr
，
l
，
（
l
+
r
）
/
2
），
query
（
now
*
2
+
1
，
ql
，
qr
，
（
l
+
r
）
/
2
+
1
，
r
））；
}
public
：
segtree
（
int
n
）{
this
->
n
=
n
；
v
=
vector
<
T
>
（
n
<<
2
，
e
（））；}
void
set
（
int
l
，
T
x
）
{
set
（
1
，
l
，
1
，
n
，
x
）；
}
T
query
（
int
l
，
int
r
）
{
return
query
（
1
，
l
，
r
，
1
，
n
）；}
}；
int
main
（）
{
segtree
<
int
，
［］（
int
x
，
int
y
）{
return
x
+
y
；}，
［］（）{
return
0
；}
>
s
（
5
）；
s
。
set
（
2
，
3
）；
s
。
set
（
3
，
4
）；
cout
<<
s
。
query
（
1
，
3
）
<<
‘\n’
；
// 7
return
0
；
}
線段樹II 區間修改+區間查詢
帶懶標記的線段樹需要滿足的條件：
任意兩個變換的複合也是一個變換。
存在恆等變換。
由於允許修改操作延遲更新，我們需要在結點上做標記。假設
中每一種變換都可以用一個
元組
表示（記該變換為
），則可以用這個
元組作為懶標記。
線上段樹 I 的基礎上，我們需要補充的是：
mapping函式。給定元素
和懶標記
，返回
composition函式，說明兩個懶標記如何疊加。給定
，返回使得
成立的
恆等變換
，如果一個點沒有打上懶標記，它所對應的變換應當讓任意的
變為其本身。記此時的懶標記狀態為
。
程式碼相應補充為：
template
<
typename
T
，
auto
op
，
auto
e
，
typename
F
，
auto
mapping
，
auto
composition
，
auto
e1
>
class
lazy_segtree
{
int
n
；
vector
<
T
>
v
；
vector
<
F
>
lazy
；
void
pushup
（
int
k
）
{
v
［
k
］
=
op
（
v
［
k
*
2
］，
v
［
k
*
2
+
1
］）；
}
void
pushdown
（
int
k
，
int
l
，
int
r
）
{
v
［
k
］
=
mapping
（
v
［
k
］，
lazy
［
k
］，
l
，
r
）；
if
（
l
！=
r
）
{
lazy
［
k
*
2
］
=
composition
（
lazy
［
k
*
2
］，
lazy
［
k
］）；
lazy
［
k
*
2
+
1
］
=
composition
（
lazy
［
k
*
2
+
1
］，
lazy
［
k
］）；
}
lazy
［
k
］
=
e1
（）；
}
void
modify
（
int
now
，
int
ql
，
int
qr
，
int
l
，
int
r
，
F
x
）
{
pushdown
（
now
，
l
，
r
）；
if
（
l
>
qr
||
r
<
ql
）
return
；
if
（
l
>=
ql
&&
r
<=
qr
）
{
lazy
［
now
］
=
x
；
pushdown
（
now
，
l
，
r
）；
return
；
}
modify
（
now
*
2
，
ql
，
qr
，
l
，
（
l
+
r
）
/
2
，
x
）；
modify
（
now
*
2
+
1
，
ql
，
qr
，
（
l
+
r
）
/
2
+
1
，
r
，
x
）；
pushup
（
now
）；
}
T
query
（
int
now
，
int
ql
，
int
qr
，
int
l
，
int
r
）
{
pushdown
（
now
，
l
，
r
）；
if
（
l
>
qr
||
r
<
ql
）
return
e
（）；
if
（
l
>=
ql
&&
r
<=
qr
）
return
v
［
now
］；
return
op
（
query
（
now
*
2
，
ql
，
qr
，
l
，
（
l
+
r
）
/
2
），
query
（
now
*
2
+
1
，
ql
，
qr
，
（
l
+
r
）
/
2
+
1
，
r
））；
}
public
：
segtree
（
int
n
）
{
this
->
n
=
n
；
v
=
vector
<
T
>
（
n
<<
2
，
e
（））；
lazy
=
vector
<
F
>
（
n
<<
2
，
e1
（））；
}
void
modify
（
int
l
，
int
r
，
F
x
）
{
modify
（
1
，
l
，
r
，
1
，
n
，
x
）；
}
T
query
（
int
l
，
int
r
）
{
return
query
（
1
，
l
，
r
，
1
，
n
）；
}
}；
在編寫模板的時候，有以下幾個可以探討的問題。
是否線上段樹內儲存結點的左右端點資訊
如果儲存的話，遞迴時就會少兩個引數。這裡沒有選擇儲存
很多時候，mapping函式不僅需要 結點值
和懶標記
，還需要區間的端點
，才能進行更新。例如區間加的懶標記
維護區間和，結點的實際值應當是
。
以下是ac-library中的做法，將結點設定為結構體
struct
S
{
int
val
；
int
size
；
}；
實際做題的時候，為了程式設計速度，可以修改mapping函式，將 l 和 r 作為函式引數傳入。
例題
P3372 【模板】線段樹 1
題意：支援區間加、區間和查詢。
分析：需要確定以下引數：
T：維護的元素的型別，這裡是 long long
op：在區間和查詢中，集合中的兩個元素如何進行運算，這裡直接將兩個元素相加。
集合的單位元，即
，這裡是
。
F：用一個多元組
唯一地確定一個變換
，這裡的區間加操作，用一個整數
表示整個區間被增加的數值。
mapping：由區間中儲存的值、其懶標記和區間左右端點，求得區間的真實值。本題的公式是：結點值
加上懶標記與區間長度的乘積。
composition：兩個懶標記
對應的變換的複合
，在
時間求出對應的
。這裡直接將兩個懶標記相加即可。
恆等變換
，一個數增加
還是它本身，即此時的懶標記狀態為
。
程式碼：
lazy_segtree
<
ll
，
［］（
ll
x
，
ll
y
）
{
return
x
+
y
；
}，
［］（）{
return
0
；}，
ll
，
［］（
ll
x
，
ll
t
，
int
l
，
int
r
）
{
return
x
+
（
r
-
l
+
1
）
*
t
；
}，
［］（
ll
t1
，
ll
t2
）
{
return
t1
+
t2
；
}，
［］（）{
return
0
；}
>
s
（
n
）；
P3373 【模板】線段樹 2
題意：支援區間加、區間乘、區間和查詢。
分析：與上一題不同的是，這裡的懶標記需要儲存兩個引數
。
mapping：
欽定
先乘後加，即結點的真實值是當前值 先乘以 mul 再加上 add * size
composition：在兩個懶標記合併時，一個數
先執行了
，變為
再執行
，變為
合變換相當於執行了一次
。
恆等變換id是
程式碼：
由於本題需要取模，所以呼叫了已經寫好的mint類
也可以手動取模。
struct
F
{
mint
mul
；
mint
add
；
}；
lazy_segtree
<
mint
，
［
&
］（
mint
x
，
mint
y
）
{
return
x
+
y
；
}，
［］（）{
return
mint
（
0
）；}，
F
，
［
&
］（
mint
x
，
F
t
，
int
l
，
int
r
）
{
return
x
*
t
。
mul
+
（
r
-
l
+
1
）
*
t
。
add
；
}，
［
&
］（
F
t1
，
F
t2
）
->
F
{
return
{（
t1
。
mul
*
t2
。
mul
），
（
t1
。
add
*
t2
。
mul
+
t2
。
add
）}；
}，
［］（）
->
F
{
return
{
1
，
0
}；}
>
s
（
n
）；
P1253 ［yLOI2018］ 扶蘇的問題
題意：支援區間加、區間賦值、區間最大值查詢。
分析：
懶標記為二元組
，
表示區間加的數，
表示區間賦值的數
注意，區間賦值是
沒有恆等變換
的，所以我們
欽定
，將
作為懶標記的預設值。
composition：
（注：下面的
是
，
表示任意值）
連續兩次區間加：
先區間賦值，再區間加：
任意操作後，區間賦值：
mapping：
注意到懶標記中至多僅有一個不是預設值。如果第一維的區間加標記
，則真實的最大值是當前值 + a
如果第二維的區間賦值標記
，則真實的最大值是
。
程式碼：
struct
F
{
ll
add
，
cover
；}；
using
ll
=
long
long
；
const
ll
inf
=
1e18
；
lazy_segtree
<
ll
，
［
&
］（
ll
x
，
ll
y
）
{
return
max
（
x
，
y
）；
}，
［］（）{
return
-
inf
；}，
F
，
［
&
］（
ll
x
，
F
t
，
int
l
，
int
r
）
{
if
（
t
。
cover
！=
inf
）
return
t
。
cover
；
else
return
x
+
t
。
add
；
}，
［
&
］（
F
t1
，
F
t2
）
->
F
{
if
（
t2
。
cover
！=
inf
）
return
{
0
，
t2
。
cover
}；
else
{
if
（
t1
。
cover
！=
inf
）
return
{
0
，
t1
。
cover
+
t2
。
add
}；
else
return
{
t1
。
add
+
t2
。
add
，
inf
}；
}
}，
［］（）
->
F
{
return
{
0
，
inf
}；}
>
s
（
n
）；
（藍橋杯國賽）2556。 第八大奇蹟（連結為acwing）
題意：單點修改，區間8th查詢。
分析：由於是單點修改，所以不需要懶標記。
本題好像有些卡常，vector不開O2比較難透過，所以 T 取了 array
需要確定以下引數：
T：維護的元素的型別，每一個區間需要維護其最大的8個元素，所以是array
op：兩個array歸併排序合併後，取最大的8個元素
集合的單位元，即
，這裡是{0，0，0，0，0，0，0，0}
程式碼：
array
<
int
，
8
>
e
（）{
return
{
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
}；}
auto
op
（
array
<
int
，
8
>
arr1
，
array
<
int
，
8
>
arr2
）{
int
t1
=
7
，
t2
=
7
；
int
cnt
=
8
；
array
<
int
，
8
>
res
；
while
（
1
）
{
if
（
t1
>=
0
&&
（
t2
==
-
1
||
arr1
［
t1
］
>=
arr2
［
t2
］）
）
{
res
［
——
cnt
］
=
（
arr1
［
t1
——
］）；
}
else
{
res
［
——
cnt
］
=
（
arr2
［
t2
——
］）；
}
if
（
cnt
==
0
）
return
res
；
}
}；
int
main
（）
{
int
n
，
m
；
cin
>>
n
>>
m
；
segtree
<
array
<
int
，
8
>
，
op
，
e
>
s
（
n
）；
。。。
}
接下來是一些需要進行一些變換的線段樹題目（待更新）。
P1438 無聊的數列
題意：支援區間加一個等差數列，單點查詢。
有些時候，區間修改操作，對於每一個數的修改規則是不同的，例如本題中，區間第一個數增加
，第二個數增加
，這樣就不符合上面對於“區間修改操作”的約定：
區間修改。給定
和變換函式
，將區間內所有的元素進行變換，即
（變換函式對於每一個元素是不同的）
實際上，此時我們還是可以使用懶標記的，只不過它在pushdown的過程中可能並不能原樣下傳，例如以
作為區間
的懶標記，表示一個區間被增加了首項為
，公差為
的等差數列，但當懶標記下傳時，就要變成：
左孩子
![[l,\frac{l+r}{2}]](https://img.heatask.com/upload/website_attach/EIEVUreWdo+ZkpUcU7MjQ6PmUrd8TosjBzGVTTcr4VCIVHoI5gzdkNV3byzMlZyBl5CYCpNme4W8ZNwKVyCn+DP9zvNKH2f2=.jpeg)
，區間加上了一個首項為
，公差為
的等差數列；
右孩子
![[\frac{l+r}{2}+1,r]](https://img.heatask.com/upload/website_attach/gMEfcGanm1X5_1_nSfvng2F2y3G891BT_xGfaVYszIsEj=+82C-tHkH8iGNlIShEhFC2Q7REPevEHGT3wAQlTwTEbTV5j2QvHSDqz.jpeg)
，區間加上了一個首項為
，公差為
的等差數列。
這樣來看，可以再傳入一個 split 函式，描述如何將一個懶標記“分裂”，不過，如果傳入的引數過多，反而使得模板臃腫，最好根據實際問題的需求，再對模板做一些簡單的修改。
template
<
typename
T
，
auto
op
，
auto
e
，
typename
F
，
auto
mapping
，
auto
composition
，
auto
split
，
auto
e1
>
class
lazy_segtree
{
。。。
if
（
l
！=
r
）
{
auto
［
lazy1
，
lazy2
］
=
split
（
lazy
［
k
］，
l
，
r
）；
lazy
［
k
*
2
］
=
composition
（
lazy
［
k
*
2
］，
lazy1
）；
lazy
［
k
*
2
+
1
］
=
composition
（
lazy
［
k
*
2
+
1
］，
lazy2
）；
}
。。。
}
因為本題中，對於區間而言，懶標記是可以疊加的，採用上述方式就可以支援區間查詢。不過在下面的分析中，還是採用差分陣列的方式。
分析：
考慮維護差分陣列
，則：如果給一個區間加上等差數列，每個元素和上一個元素的差值就增加
（首個元素與上一個元素的差值增加
，最後一個元素的下一個元素，與最後一個元素的差值增加
），這樣，就可以透過
次區間修改來實現（其中
次是單點修改。）
而，一個元素的值，就是差分陣列中對應的字首和。
問題轉化為普通的
區間修改區間求和
的問題。
M 數硬幣
題意：區間加，區間求gcd。
分析：本題如果以
作為懶標記，composition疊加比較容易，但是mapping函式無法輕鬆在
解決。
考慮到等式
，我們可以用兩棵線段樹分別維護
單點的值
，比較容易。
，這裡維護差分陣列
，則區間
增加
，只要兩次單點修改，即
增加
，
減少
。
將兩者再取gcd就可以得到答案。
CF446C DZY Loves Fibonacci Numbers
題意：支援區間加斐波那契數列（
），區間求和。
P1471 方差
