# Lichao Segment Tree
## Giới Thiệu
- Trước khi đọc bài viết này, đọc giả cần trang bị một số kiến thức sau để có thể hiểu rõ về Lichao Segment Tree:
- [Segment Tree](https://wiki.vnoi.info/algo/data-structures/segment-tree-basic.md) - Đây là kiến thức quan trọng nhất để hiểu được bài viết này, ta cần có kiến thức về các bài toán Segment Tree cơ bản, [Walk On Segment Tree](https://leduythuccs.github.io/2020-07-10-Binary-Search-on-Segment-Tree/).
- [Pointer](https://wiki.vnoi.info/languages/cpp/pointers) (con trỏ) - Ta cần hiểu về Pointer để thực hiện $1$ trong $2$ cách cài đặt bên dưới, nếu các bạn chọn cách cài đặt theo Trie (theo tác giả là dễ hơn) thì có thể bỏ qua con trỏ nhưng đây cũng là một cách cài đặt rất hay.
- [Trie](https://wiki.vnoi.info/algo/data-structures/trie) - Đây là cách cài đặt còn lại của bài, đây cũng là thứ tác giả thường dùng để cài Lichao Segment Tree.
- Ngoài ra đó còn có $2$ thuật toán sau được sử dụng trong phần bài tập ví dụ phía dưới.
- [Centroid Decomposition](https://wiki.vnoi.info/algo/graph-theory/centroid-decomposition.md) - Đây là một thuật toán thường dùng để xử lí các bài toán về đường đi trên cây.
- [Rerooting](https://wiki.vnoi.info/algo/dp/treedp) - Đây là một kĩ thuật hay để giải quyết các bài toán DP trên cây.
- **"Lichao Segment Tree"** hay còn được biết đến là **"Cây phân đoạn trên tập đoạn thẳng"** tại Việt Nam là một cấu trúc dữ liệu để xử lí một số truy vấn trên một tập các hàm cùng dạng, mỗi cặp hàm thuộc tập này chỉ giao nhau tại duy nhất $1$ điểm (ví dụ như cùng là đường thẳng: $f(x) = a*x+b$).
- Các truy vấn phổ biến thường thấy trong các bài toán dùng Lichao Segment Tree:
**1. Truy vấn thêm:** Thêm một hàm chưa xuất hiện trong tập lên cây.
**2. Truy vấn tìm max, min:** Cho số $x$, tìm hàm $f(x)$ thuộc tập các hàm đã thêm sao cho $f(x)$ max / min.
Lichao Segment Tree có thể thực hiện $2$ truy vấn này trong độ phức tạp $O(\log{n})$.
## Bài Toán Điển Hình
- **Đề bài:** Cho tập $S$ trống, thực hiện $Q$ lần $1$ trong $2$ truy vấn sau:
- $+$ $a$ $b$ : Thêm hàm $f(x) = a*x+b$ vào tập S.
- $query$ $a$ : Tìm max $f_i(a)$ với mọi $f_i(x)$ $\in S$.
- **Giới hạn:** $1 \leq Q \leq 10^5, 1 \leq a,b \leq 5*10^4$.
- Trước hết ta sẽ xem điều gì xảy ra khi ta thêm 1 hàm vào cây Lichao (ở đây ta sẽ chỉ xét tới trường hợp hàm thêm vào là một đường thẳng và ta đang tìm max trên cây):
- Xét đường thẳng màu xanh là đường thẳng đã có trên cây, đường thẳng màu đỏ là đường thẳng ta sẽ thêm vào, ta sẽ có $2$ trường hợp như sau:
- Ta dễ thấy rằng các điểm nằm phía bên trái điểm giao của $2$ đoạn, đáp án sẽ luôn lựa chọn đường thẳng màu đỏ. Thế nhưng các điểm nằm phía bên phải điểm giao này sẽ chọn đường thẳng màu xanh do kết quả khi này của đường thẳng màu xanh sẽ lớn hơn khi đưa vào hàm có đường thẳng màu đỏ.
- Qua hình ảnh này các bạn có thể thấy rõ hơn những gì vừa nói, ở phía bên trái điểm giao, khi ta chọn một giá trị $x$ thì giá trị trả về của giá trị $x$ này trên đường màu đỏ luôn ở trên so với đường màu xanh.
- Ngược lại ở phía bên phải điểm giao, giá trị trả về của giá trị $x$ của đường màu đỏ luôn bé hơn giá trị của đường màu xanh.
- Do đó khi ta thêm đường thẳng màu đỏ vào và đường thẳng tối ưu của đoạn $[l...r]$ khi đó là đường thẳng màu xanh như hình, lúc này các điểm phía bên phải điểm giao sẽ giữ nguyên đường thẳng đại diện, điểm phía bên trái điểm giao sẽ đổi đường thẳng đại diện thành đường thẳng màu đỏ.
- Từ đây ta có thể thấy, lúc này ta chỉ cần khi xét đoạn $[l..r]$, ta sẽ xét giá trị mà $2$ hàm trả về với $3$ vị trí là $l$, $mid$, $r$.
- Chi tiết hơn, bằng việc thực hiện tương tự cách update trên Segment Tree, ta chỉ cần đặt một điểm là $mid$ (trên hình chính là đường màu trắng ở giữa), với trường hợp trên thì ta sẽ tiến hành update tiếp xuống phía bên trái khi giá trị trả về của hàm xanh biển bé hơn giá trị trả về của hàm đỏ với đầu vào là $l$ nhưng lớn hơn khi đầu vào là $mid$ hoặc giá trị trả ra với đầu vào là $mid$ lớn hơn khi đầu vào là $l$.
- Trường hợp này ta sẽ thực hiện tương tự với trường hợp trên, chỉ khác rằng đoạn cần giữ lại sẽ nằm trên khoảng bên trái của đường màu trắng, ta thực hiện thay đổi ở khoảng bên phải.
- Bây giờ đến với cách ta lấy được giá trị $f(x)$ max / min sau khi ta đã thêm các hàm lên cây. Từ cách ta thêm hàm lên cây, ta có thể thấy rằng khi ta lấy giá trị $f(x)$ ta chỉ cần tìm vị trí của $x$ trên cây rồi lấy ra hàm đang nằm trên điểm đó. Đây thực tế chính là Walk trên cây Segment Tree.
- Do các thao tác như ta đã thấy tương tự với bài toán tương tự với các thao tác trên cây Segment Tree, do đó độ phức tạp của Lichao Segment Tree cũng tương tự Segment Tree bình thường $\rightarrow$ $O(\log{n})$.
- Cách hoạt động này cũng tương tự với các hàm khác đường thẳng thỏa mãn tính chất đã nêu khi giới thiệu.
## Cách Cài Đặt
- Ở đây ta chỉ đang xét đến trường hợp hàm thêm vào là đường thẳng (các hàm thêm vào khác đường thẳng (và thỏa mãn điều kiện đã nói ở phần giới thiệu) cũng sẽ làm tương tự), nên trước hết ta sẽ `struct line` để dễ dàng thao tác hơn:
```cpp
struct line
{
ll a, b; line() {} line(ll a, ll b) : a(a), b(b) {}
ll operator() (ll x) {return a*x+b;}
};
```
- **Lưu ý:** Nếu bài bạn đang làm cần đến đầu vào là hàm khác đường thẳng (và thỏa mãn tính chất ở phần giới thiệu đã nêu) thì lúc này bạn chỉ cần chỉnh lại phần `struct line` này thành hàm bạn đang xét tới là được.
- Ở đây tác giả sẽ giới thiệu đến mọi người cách cài đặt Lichao Segment Tree sao cho có thể dùng "ăn liền" trong nhiều bài toán nhất có thể, do đó phần code sau đây sẽ sử dụng tới cách cài đặt Implicit Segment Tree hay còn gọi là Dynamic Segment Tree để cây có thể bao khoảng rộng hơn việc cài Segment Tree bình thường (việc sử dụng Segment Tree bình thường để cài hoàn toàn xử lí được các bài toán có khoảng giá trị cần lấy to (lấy hàm $f(x)$ với $x$ lớn) bằng cách song ánh các giá trị này sang 1 tập giá trị bé hơn (tương tự nén số) nhưng cách này không "ăn liền" và đôi lúc dễ sai hơn nên sẽ không được giới thiệu tại đây).
- Cách cài đặt hàm `add`:
```cpp
// cách cài đặt dùng con trỏ
void add(ll l, ll r, line nw)
{
ll m = (r+l)>>1;
bool lef = y(l) < nw(l), mid = y(m) < nw(m), rig = y(r) < nw(r);
if (mid) swap(nw, y);
if (l == r) return;
else if (lef != mid) {if (!left) {left = new node;} (*left).add(l, m, nw);}
else if (rig != mid) {if (!right) {right = new node;} (*right).add(m+1, r, nw);}
}
```
```cpp
// cách cài đặt giống với cách cài Trie
struct node {line y = line(0, 0); ll left = -1, right = -1;};
vector<node> v;
// với cách này cần thêm mảng v trên để lưu node chứa line và 2 nhánh 2 bên
void q_add(ll l, ll r, line nw, ll id = 0)
{
ll m = (r+l)>>1;
bool lef = v[id].y(l) < nw(l), mid = v[id].y(m) < nw(m), rig = v[id].y(r) < nw(r);
if (mid) swap(nw, v[id].y);
if (l == r) return;
else if (lef != mid)
{
if (v[id].left == -1) {v[id].left = v.size(); v.emplace_back();}
q_add(l, m, nw, v[id].left);
}
else if (rig != mid)
{
if (v[id].right == -1) {v[id].right = v.size(); v.emplace_back();}
q_add(m+1, r, nw, v[id].right);
}
}
```
- Ở hàm `add` này, trước hết ta sẽ tiến hành so sánh kết quả của hàm đang đẩy vào với đầu vào là $l, mid, r$, nếu kết quả khi hàm mới thêm vào với đầu vào là $mid$ tốt hơn hàm đang có với cùng đầu vào, ta sẽ swap $2$ hàm này lại.
- Như đã nói phía bên trên, ta sẽ thấy chỉ có tối đa $1$ trong $2$ phía cần đến hàm đang có ở đoạn hiện tại trên cây. Do đó việc swap này sẽ giúp ta Walk trên cây mà vẫn đi qua đầy đủ các hàm cần xét. Ngược lại cũng sẽ có $1$ trong $2$ phía không cần đến hàm đang xét hiện tại nhưng vẫn cần đến hàm mới thêm vào nên việc cài đặt như trên hoàn toàn phù hợp với việc ta Walk trên cây trong hàm `get` phía dưới.
- Cách cài đặt hàm `get`:
```cpp
// cách cài đặt dùng con trỏ
ll get(ll l, ll r, ll x)
{
ll m = (r+l)>>1, val = y(x);
if (x < m && left) val = max(val, (*left).get(l, m, x));
if (x > m && right) val = max(val, (*right).get(m+1, r, x));
return val;
}
```
```cpp
// cách cài đặt giống với cách cài Trie
ll q_get(ll l, ll r, ll x, ll id = 0)
{
ll m = (r+l)>>1, val = v[id].y(x);
if (x < m && v[id].left != -1) val = max(val, q_get(l, m, x, v[id].left));
if (x > m && v[id].right != -1) val = max(val, q_get(m+1, r, x, v[id].right));
return val;
}
```
- Ở hàm `get` này sẽ không giải thích gì thêm vì thực tế hàm này chỉ đơn giản là ta Walk trên cây Segment Tree.
## Áp Dụng Bài Toán Điển Hình
- Không giống như Segment Tree bình thường, các bài toán sử dụng Lichao Segment Tree thường không thể xử lí cả bài trên cây được, thường Lichao Segment Tree chỉ được dùng để làm $1$ phần của bài toán. Dạng bài sử dụng Lichao Segment Tree nhiều nhất thường là bài toán DP, ta sẽ sử dụng Lichao để tìm $1$ phần đáp án trong $O(\log{n})$.
- Ví dụ bài toán dưới đây:
[Codeforces 1083E: The Fair Nut and Rectangles](https://codeforces.com/problemset/problem/1083/E)
- **Tóm tắt đề bài:** Cho $n$ hình chữ nhật có tọa độ các đỉnh là $(0,0), (0,y_i), (x_i,y_i), (x_i,0)$. Với mỗi hình chữ nhật đã cho, cho giá trị $a_i$ tương ứng với hình chữ nhật thứ $i$. Yêu cầu chọn một số hình chữ nhật trong $n$ hình chữ nhật này sao cho giá trị của bộ đã chọn là lớn nhất. Biết các hình chữ nhật không bao nhau, giá tri của một bộ hình chữ nhật là tổng diện tích phần hợp của các hình thuộc bộ trừ đi tổng các giá trị $a_i$ thuộc bộ.
- **Giới hạn:** $1 \leq n \leq 10^6, 1 \leq x_i, y_i \leq 10^9, 0 \leq a_i \leq x_i*y_i$.
- **Lời giải:**
- Trước hết, ta nhận thấy rằng đề bài cho tập $n$ hình chữ nhật không bao nhau, từ đây ta có thể thấy rằng nếu ta sắp xếp các hình chữ nhật theo $x_i$ thì nếu dãy $x_1, x_2, x_3,...,x_{n-1},x_n$ tăng thì $y_1, y_2, y_3,...,y_{n-1}, y_n$ giảm.
- Gọi $dp_i$ là đáp án tối ưu cho $1$ tập con các phần tử của tập $i$ phần tử đầu.
- Ta có thể thấy do sau khi sort theo $x$, lúc này khi ta thêm hình chữ nhật thứ $i$ vào $1$ tập hình chữ nhật nào đó, thực tế lúc này do các hình chữ nhật không đan nhau, diện tích tăng thêm lúc này là $x_i*y_i-x_j*y_i$ với $j$ là hình chữ nhật cuối cùng của tập trên (hình chữ nhật có $x$ lớn nhất của tập thêm vào).
- Từ đây ta dễ dàng viết được công thức $dp$ của bài: $dp_i = \max_{1 \leq j < i}{(dp_j+x_i*y_i-x_j*y_i)}$.
- Vậy ta áp dụng Lichao Segment Tree vào bài toán này như nào?
- Trước hết khi xét đến phần tử $i$, ta sẽ có luôn giá trị cho $x_i*y_i$, như vậy thực tế thì công thức $dp$ của ta có thể viết lại như sau:
$dp_i = x_i*y_i + \max_{1 \leq j < i}{(dp_j-x_j*y_i)}$.
- Từ đây ta có thể thấy rằng phần $dp_j-x_j*y_i$ thực tế nhìn giống với $f(x) = a*x+b$ khi sắp xếp lại thành $-x_j*y_i+dp_j$.
- Lúc này ta chỉ cần thêm các đường thẳng $f_j(x) = -x_j*x+dp_j$ với mọi $j < i$ rồi tính $dp_i$ nhanh bằng cách lấy max / min trên Lichao Segment Tree.
- Hình ảnh minh họa:
- Hình ảnh này cho thấy phần tăng thêm của diện tích hợp bởi các hình chữ nhật nếu cho vào theo thứ tự từ $1$ đến $3$ (đương nhiên là giá trị của $x_i$ cũng tăng dần, $y_i$ giảm dần từ hình thứ $1$ đến hình $3$).
- Code ví dụ:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mxn = 1e6+7;
struct lichao_segment_tree
{
static const ll l = -1e9, r = 1e9, inf = 1e18;
struct line
{
ll a, b; line() {} line(ll a, ll b) : a(a), b(b) {}
ll operator() (ll x) {return a*x+b;}
};
struct node
{
line y = line(0, 0);
node *left = nullptr, *right = nullptr;
void add(ll l, ll r, line nw)
{
ll m = (r+l)>>1;
bool lef = y(l) < nw(l), mid = y(m) < nw(m), rig = y(r) < nw(r);
if (mid) swap(nw, y);
if (l == r) return;
else if (lef != mid) {if (!left) {left = new node;} (*left).add(l, m, nw);}
else if (rig != mid) {if (!right) {right = new node;} (*right).add(m+1, r, nw);}
}
ll get(ll l, ll r, ll x)
{
ll m = (r+l)>>1, val = y(x);
if (x < m && left) val = max(val, (*left).get(l, m, x));
if (x > m && right) val = max(val, (*right).get(m+1, r, x));
return val;
}
} st;
void add(ll a, ll b) {st.add(l, r, {a, b});}
ll get(ll x) {return st.get(l, r, x);}
} st;
struct rec {ll x, y, a;};
struct cmp {bool operator() (rec a, rec b) {return a.x < b.x;}};
ll dp[mxn];
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n; cin >> n; vector<rec> v;
for (ll i = 1; i <= n; i++)
{
ll x, y, a; cin >> x >> y >> a;
v.pb({x,y,a});
}
sort(v.begin(),v.end(),cmp());
dp[0] = v[0].x*v[0].y-v[0].a;
st.add(-v[0].x,dp[0]);
for (ll i = 1; i < n; i++)
{
dp[i] = v[i].x*v[i].y-v[i].a;
ll opt = st.get(v[i].y);
dp[i] += max(0LL,opt);
st.add(-v[i].x,dp[i]);
}
cout << *max_element(dp,dp+n);
}
```
- Đây cũng là cách giải chung của các bài toán DP cần sử dụng tới Lichao Segment Tree.
- Các bước giải có thể giải theo $1$ hướng như sau:
1. Dựng công thức DP.
2. Biến đổi công thức DP sang dạng: $dp_i = g(i)+f(i)$ với $g(i)$ là hàm lưu các giá trị có thể tính trực tiếp khi ta có $i$ mà không cần bất kì giá trị $j$ nào khác, $f(i)$ là hàm max / min của $i$ khi áp vào $1$ hàm nào đó đã được thêm vào trước. Như bài toán vừa ví dụ thì $g(i) = x_i*y_i$ và $f(i) = \max_{1 \leq j < i}{(dp_j-x_j*y_i)}$.
3. Khi đã biến đổi công thức DP xong, ta chỉ cần thêm các hàm vào Lichao Segment Tree để lấy đáp án mỗi lần duyệt xử lí DP.
## Các Bài Toán Tương Tự
[Codeforces 319C: Kalila and Dimna in the Logging Industry](https://codeforces.com/problemset/problem/319/C)
- **Tóm tắt đề bài:** Cho $n$ cây có độ dài lần lượt là $a_1, a_2, a_3,..., a_n$. Mỗi lần sử dụng cưa lên cây thứ $i$, độ cao cây $i$ giảm đi $1$ đơn vị. Mỗi lần sử dụng xong đều phải sạc lại, chi phí sạc dựa theo chỉ số của cây đã bị cắt hết gần nhất, nếu cây bị cắt hết gần nhất là $j$, chi phí sạc là $b_j$. Nếu chưa có cây nào bị cắt hết, lúc này ta không thể sạc lại cưa. Ban đầu cái cưa đã được sạc. Yêu cầu tìm chi phí sạc ít nhất.
- **Giới hạn:** $1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9, 0 \leq b_i \leq 10^9, a_1 = 1, b_n = 0, a_1 < a_2 < ... < a_n,$ $b_1 > b_2 > ... > b_n$.
- **Lời giải:**
- Gọi $dp_i$ là chi phí để cắt hết cây $i$, ta dễ thấy được $dp_i = dp_j+b_j*a_i$ với $j$ là cây gần nhất bị cắt hết.
- Qua công thức DP trên, như ở phần trước đã nói, ta chỉ cần chuyển công thức này sang dạng $1$ hàm thỏa mãn là $f_j(x) = b_j*x+dp_j$ thì ta có thể áp dụng Lichao Segment Tree vào để hoàn thành bài toán.
- Code ví dụ:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mxn = 1e5+7;
struct lichao_segment_tree
{
// template Lichao Segment Tree
} st;
ll a[mxn], b[mxn], dp[mxn];
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n; cin >> n;
for (ll i = 1; i <= n; i++) cin >> a[i];
for (ll i = 1; i <= n; i++) cin >> b[i];
st.add(b[1], 0);
for (ll i = 2; i <= n; i++)
{
dp[i] = st.get(a[i]);
st.add(b[i], dp[i]);
}
cout << dp[n];
}
```
[Codeforces 631E: Product Sum](https://codeforces.com/problemset/problem/631/E)
- **Tóm tắt đề bài:** Cho một mảng $A$ gồm $n$ phần tử, giá trị của mảng là $\sum_{i = 1}^n{A_i*i}$. Ta được phép thực hiện phép di chuyển sau chính xác $1$ lần: Chọn một phần tử và di chuyển nó đến bất kì vị trí nào trên mảng (có thể là giữ nguyên vị trí, về đầu, về cuối). Tính giá trị lớn nhất có thể của mảng sau khi thực hiện phép di chuyển.
- **Giới hạn:** $2 \leq n \leq 2*10^5, |a_i| \leq 10^6$.
- **Lời giải:**
- Trước hết ta có một số đánh giá về giá trị của mảng qua phép di chuyển:
1. Tổng mảng khi giữ nguyên vị trí của $i'$: $\sum_{i = 1}^n{A_i*i}$.
2. Khi chuyển phần tử $i'$ sang vị trí $j$ với $j > {i'}$:
- Đoạn từ $1$ đến $i'-1$ giữ nguyên $\rightarrow$ $\sum_{i = 1}^{i'-1}{A_i*i}$.
- Đoạn từ $j+1$ đến $n$ giữ nguyên $\rightarrow$ $\sum_{i = j+1}^n{A_i*i}$.
- Thay đổi đoạn từ $i'$ đến $j$:
* Tổng đoạn từ $i'+1$ đến $j$ thành $\sum_{i = {i'+1}}^{j}{A_i*{(i-1)}}$.
* Tổng đoạn từ $i'$ đến $i'$ thành $A_i*j$.
- Hoạt ảnh minh họa sự thay đổi:
- Qua hoạt ảnh này ta có thể thấy rõ phần $* i$ thay đổi ra sao, như trên, phần $A_2, A_3$ đã giảm đi $A_2 + A_3$, phần $A_1$ từ $A_1 * 1$ chuyển thành $A_1 * 3$, đúng như những gì đã đề cập ở phần thay đổi ở tổng khi di chuyển.
- Như vậy, nếu di chuyển phần tử $i'$ sang vị trí $j$ với $j > {i'}$ thì tổng mới sẽ là:
$\sum_{i = 1}^{i'-1}{A_i*i} + \sum_{i = j+1}^n{A_i*i} + \sum_{i = {i'+1}}^{j}{A_i*{(i-1)}} + A_i*j$.
$= \sum_{i = 1}^n{A_i*i} - \sum_{i = {i'+1}}^{j}{A_i}-A_{i'}*{i'}+A_{i'}*{j}$.
$= \sum_{i = 1}^n{A_i*i} - \sum_{i = {i'+1}}^{j}{A_i}+A_{i'}*{(j-i')}$.
$= \sum_{i = 1}^n{A_i*i} - \sum_{i = 1}^{j}{A_i} + \sum_{i = 1}^{i'}{A_i}+A_{i'}*{(j-i')}$.
3. Khi chuyển phần tử $i'$ sang vị trí $j$ với $j < i'$:
- Phần này ta thực hiện tương tự với phần số $2$.
- Ta có thể thấy, bất kể khi ta di chuyển phần tử $i'$ như thế nào, tổng mới sẽ luôn có phần $\sum_{i = 1}^n{A_i*i}$ giữ nguyên, do đó ta chỉ cần quan tâm đến phần còn lại của tổng mới: $- \sum_{i = 1}^{j}{A_i} + \sum_{i = 1}^{i'}{A_i}+A_{i'}*{(j-i')}$. (Ví dụ khi chuyển từ $i'$ sang $j$ với $j > i'$).
- Ta có thể thấy phần còn lại của tổng mới $- \sum_{i = 1}^{j}{A_i} + \sum_{i = 1}^{i'}{A_i}+A_{i'}*{(j-i')}$ nếu ta sắp xếp lại thành ${(j-i')}*A_{i'} - \sum_{i = 1}^{j}{A_i} + \sum_{i = 1}^{i'}{A_i}$, từ đây ta lại thấy rằng mỗi phần này đều chứa $-A_{i'}*{i'}$ và $\sum_{i = 1}^{i'}{A_i}$ thì nếu ta rút gọn thành $j*{A_{i'}}-\sum_{i = 1}^{j}{A_i}$, hình dạng của phần này giống như đường thằng $f(x) = a*x+b$ với $a = {j}$ và $b = -\sum_{i = 1}^{j}{A_i}$.
- Như vậy, ta có thể thấy rằng với mỗi vị trí $i'$ để tìm được sự thay đổi tối ưu thì ta chỉ cần tìm hàm $f(x)$ tối ưu trong tập các hàm đã thêm trước đó.
- Chi tiết hơn, để tính toán vị trí $i'$ chuyển sang $j$ tối ưu mà $j > {i'}$ ta chỉ cần thêm các hàm $f_k(x) = k*{x}-\sum_{i = 1}^{k}{A_i}$ với $k$ từ $i'$ đến $n$ rồi dùng Lichao Segment Tree để tìm max $f_k(x)$, lúc này $f_k(x)$ chính là hàm $f_j(x)$ của vị trí $j$ tối ưu. Khi chuyển sang $j$ mà $j < {i'}$ ta cũng sẽ làm tương tự như vậy.
- Từ đây ta sẽ tìm max $\sum_{i = 1}^n{A_i*i} - \sum_{i = {i'+1}}^{j}{A_i}+A_{i'}*{(j-i')}$ với mọi $i'$.
- Đáp án của bài toán là giá trị max này trong $3$ cách di chuyển phần tử $i'$ ra trước, sau, giữ nguyên vị trí.
- Code ví dụ:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mxn = 2e5+7;
struct lichao_segment_tree
{
// template Lichao Segment Tree
} st, stt;
ll a[mxn], dp1[mxn], dp2[mxn], ans = 0;
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n; cin >> n;
for (ll i = 1; i <= n; i++) {cin >> a[i]; ans += a[i]*i; a[i] += a[i-1];}
st.add(n,-a[n]);
for (ll i = n-1; i >= 1; i--)
{
dp1[i] = -(a[i]-a[i-1])*i+a[i]+st.get(a[i]-a[i-1]);
st.add(i, -a[i]);
}
stt.add(1, 0);
for (ll i = 2; i <= n; i++)
{
dp2[i] = -(a[i]-a[i-1])*i+a[i-1]+stt.get(a[i]-a[i-1]);
stt.add(i, -a[i-1]);
}
cout << ans+max(*max_element(dp1,dp1+n+1),*max_element(dp2,dp2+n+1));
}
```
[Codeforces 1303G: Sum of Prefix Sums](https://codeforces.com/contest/1303/problem/G)
- **Tóm tắt đề bài:** Ta định nghĩa tổng của tổng tiền tố của mảng $[s_1,s_2,s_3,...,s_n]$ là $s_1+(s_1+s_2)+(s_1+s_2+s_3)+...+(s_1+s_2+s_3+...+s_n)$. Cho cây $n$ đỉnh, mỗi đỉnh chứa một số $a_i$, ta định nghĩa giá trị đường đi từ $u \rightarrow v$ là tổng của tổng tiền tố của mảng $[a_{q_1},a_{q_2},...,a_{q_k}]$ với $k$ là số đỉnh trên đường đi ngắn nhất từ $u \rightarrow v$ và $q$ là tập các đỉnh trên đường đi đấy. Tìm đường đi có giá trị lớn nhất.
- **Giới hạn:** $2 \leq n \leq 150000, 1 \leq u_i, v_i \leq n, u_i \neq v_i, 1 \leq a_i \leq 10^6$.
- **Lời giải:**
- Trước hết ta sẽ viết $1$ số định nghĩa về hàm để dễ thao tác hơn:
- $[a_1,a_2,...,a_n] + [b_1,b_2,...,b_m] = [a_1,a_2,...,a_n,b_1,b_2,...,b_m]$.
- $f([s_1,s_2,...,s_n]) = (s_1+s_2+s_3+...+s_n)$.
- $g([s_1,s_2,...,s_n]) = s_1+(s_1+s_2)+(s_1+s_2+s_3)+...+(s_1+s_2+s_3+...+s_n).$
- $LCA(A,B) =$ Tổ tiên chung gần nhất của $A$ và $B$.
- Gọi $A = [s_1,s_2,...,s_n]$, ta có:
- $g(A) = \sum_{i = 1}^{n}{\sum_{j = 1}^{i}{s_j}} = \sum_{i = 1}^{n}{s_i*(n-i+1)}.$
- Việc bài toán này là một bài toán xử lí trên đường đi trên cây, điều này gợi ý cho chúng ta rất nhiều về thuật toán phân rã trọng tâm trên cây (hay còn gọi là Centroid Decomposition). Lúc này thực tế ta chỉ cần tìm cách tính giá trị của đường đi $A \rightarrow LCA(A,B) \rightarrow B$.
- Bây giờ khi ta xét đường đi $A \rightarrow LCA(A,B) \rightarrow B$, ta cần xử lí $2$ đường đi quan trọng là $A \rightarrow LCA(A,B)$ và $LCA(A,B) \rightarrow B$ rồi tiến hành ghép chúng lại với nhau.
- Trước hết ta xem khi ta gộp $2$ mảng lại với nhau thì hàm $g([])$ bên trên sẽ thay đổi như nào:
- $g([a_1,a_2,...,a_n]) = \sum_{i = 1}^{n}{\sum_{j = 1}^{i}{a_j}} = \sum_{i = 1}^{n}{a_i*(n-i+1)}.$
- $g([b_1,b_2,...,b_m]) = \sum_{i = 1}^{m}{\sum_{j = 1}^{i}{b_m}} = \sum_{i = 1}^{m}{b_i*(m-i+1)}.$
- Đặt $[c_1,c_2,...,c_{n+m}] = [a_1,a_2,...,a_n,b_1,b_2,...,b_m]$, ta có:
$\rightarrow g([c_1,c_2,...,c_{n+m}]) = \sum_{i = 1}^{n+m}{c_i*(n+m-i+1)}.$
$\rightarrow g([c_1,c_2,...,c_{n+m}]) = \sum_{i = 1}^{n}{a_i*(n+m-i+1)}+\sum_{i = 1}^{m}{b_i*(m-i+1)}.$
$\rightarrow g([c_1,c_2,...,c_{n+m}]) = \sum_{i = 1}^{n}{a_i*(n-i+1)}+m*f([a_1,a_2,...,a_n])+\sum_{i = 1}^{m}{b_i*(m-i+1)}.$
- Từ đây ta có thể thấy khá rõ hình dáng của một hàm số bậc nhất từ công thức ghép trên, giả sử ta đang xét nửa $[b_1,b_2,...,b_m]$ và ta cần tìm nửa $[a_1,a_2,...,a_n]$ tối ưu, ta chỉ cần cố định $\sum_{i = 1}^{m}{b_i*(m-i+1)}$ rồi tìm max của phần $\sum_{i = 1}^{n}{a_i*(n-i+1)}+m*f([a_1,a_2,...,a_n])$.
- Phần $\sum_{i = 1}^{n}{a_i*(n-i+1)}+m*f([a_1,a_2,...,a_n])$ rất dễ thấy rằng đây có dạng của một hàm số $f_i(x) = a*x+b$ với $a = f([a_1,a_2,...,a_n])$ và $b = \sum_{i = 1}^{n}{a_i*(n-i+1)}$.
- Lúc này việc áp dụng thêm Lichao Segment Tree vào là vô cùng dễ, ta chỉ cần làm tương tự các bài đã ví dụ phía trên.
- Ta đã biết cách gộp $2$ mảng với nhau, việc thực hiện với $2$ đường đi cũng không khác là bao, ta chỉ cần tính mảng đường đi từ $A \rightarrow LCA(A,B)$ và $LCA(A,B) \rightarrow B$ (lưu ý thứ tự của nửa $LCA(A,B) \rightarrow B$ có quan trọng, tính ngược lại từ $B$ sẽ sai) rồi ghép chúng lại với nhau.
- Hình ảnh ví dụ về đường đi:
- Ở hình ảnh này, ta đang xét đường đi từ $12 \rightarrow 8$, đi qua $LCA(12,8) = 1$, lúc này ta có mảng $[a_1,a_2,...,a_n]$ như ở phía trên là $[a_1,a_2,a_4,a_1]$ và mảng $[b_1,b_2,...,b_m]$ là $[a_1,a_2,a_6,a_8]$.
- Lúc này ta chỉ cần xóa đi phần tử $a_1$ khỏi tập $[a_1,a_2,a_6,a_8]$ thì ta có thể tiến hành việc gộp mảng như bên trên đã đề cập.
- Sau cùng ta áp dụng điều này vào lúc ta phân rã trọng tâm thì ta sẽ giải được bài toán này.
- Code ví dụ:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 15e4+7;
struct lichao_segment_tree
{
// template Lichao Segment Tree
} st;
vector<pair<ll,ll>> vv;
ll n, a[mxn], sz[mxn], ans = 0;
bool del[mxn];
vector<vector<ll>> g(mxn);
void dfs_sz(ll u, ll v)
{
// template tính kích thước subtree
}
ll dfs_ctr(ll u, ll v, ll szx)
{
// template tìm centroid
}
void add(ll u, ll v, ll d_dp, ll u_dp, ll pfs, ll h, bool query, ll root)
{
bool ck = 1;
for (ll i : g[u])
{
if (i != v && !del[i])
{
ck = 0;
add(i,u,d_dp+pfs+a[i],u_dp+a[i]*h,pfs+a[i],h+1,query,root);
}
}
if (ck)
{
if (query) ans = max(ans, st.get(h)+d_dp+a[root]*h);
vv.pb({pfs, u_dp});
ans = max({ans,u_dp+pfs+a[root],d_dp+a[root]*h});
}
}
void upd(ll u)
{
st = lichao_segment_tree();
for (ll i = 0; i < g[u].size(); i++)
{
if (!del[g[u][i]])
{
add(g[u][i],u,a[g[u][i]],a[g[u][i]],a[g[u][i]],2,(i > 0),u);
for (pair<ll,ll> j : vv) st.add(j.fi,j.se);
vv.clear();
}
}
st = lichao_segment_tree();
for (ll i = g[u].size()-1; i >= 0; i--)
{
if (!del[g[u][i]])
{
add(g[u][i],u,a[g[u][i]],a[g[u][i]],a[g[u][i]],2,(i < (g[u].size()-1)),u);
for (pair<ll,ll> j : vv) st.add(j.fi,j.se);
vv.clear();
}
}
}
void solve(ll u)
{
dfs_sz(u,u); ll n_root = dfs_ctr(u,u,sz[u]);
upd(n_root); del[n_root] = 1;
for (ll i : g[n_root]) {if (!del[i]) solve(i);}
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (ll i = 1; i < n; i++)
{
ll ax, b; cin >> ax >> b;
g[ax].pb(b); g[b].pb(ax);
}
for (ll i = 1; i <= n; i++) cin >> a[i];
solve(1); cout << ans;
}
```
## Tìm Hàm Tối Ưu Thứ K Trên Lichao Segment Tree
- Như ở phía trên đã đề cập, ta thấy Lichao Segment Tree có thể giúp chúng ta tìm được min / max của $f(x)$ với $x$ cho trước, vậy nếu ta cần tìm giá trị max / min thứ $k$ thì Lichao Segment Tree có làm được không?
- Trước hết, cây Lichao bình thường sẽ lưu hàm tối ưu nhất cho mỗi node, như vậy hướng nghĩ tự nhiên nhất để giải quyết bài toán trên là ta sẽ lưu $k$ hàm tối ưu nhất. Thế nhưng khi xóa hàm tệ nhất khi add thêm $1$ hàm mới vào thì hàm này chưa chắc đã không được sử dụng ở cả $2$ nửa của đoạn.
- Cách xử lí lúc này lại trở nên vô cùng dễ, ta chỉ cần lưu $2*k-1$ hàm mỗi node là được.
- Vậy vì sao cách lưu này lại đúng?
- Trước hết, khi ta nhìn cách ta cài đặt cũng như cách hoạt động của một Lichao Segment Tree cơ bản, ta có thể thấy rằng một hàm chỉ được push xuống $1$ trong $2$ nửa của đoạn nếu hàm này không còn tối ưu trong nửa còn lại nữa.
- Khi một hàm được thêm vào một tập có sẵn $2*k-1$ hàm, lúc này hàm tệ nhất sẽ lớn hơn $2*k-1$ hàm. Giả sử ta có $a$ hàm tốt hơn ở phía phải, $b$ hàm tốt hơn ở phía trái. Vậy ta sẽ có $a+b=2*k-1$ hàm tốt hơn, lúc này ta có thể thấy rằng $\max{(a,b)} \geq \lceil{\frac{2*k-1}{2}} \rceil = k.$
- Điều này dẫn tới việc $1$ trong $2$ nửa không còn cần tới hàm tệ nhất ở đoạn hiện tại nữa, lúc này ta chỉ cần đẩy hàm này xuống nửa còn lại của đoạn.
- Hình minh họa:
- Như hình này (trường hợp này vẽ đường thẳng cho dễ nhìn cũng như dễ vẽ hơn) ta có thể thấy ở phía bên phải của đoạn, nếu $k = 3$ thì đường tệ nhất (đường màu cam) không là đáp án cho bất kì vị trí nào ở phía phải đường $mid$ (đường trắng).
- Cài đặt:
```cpp
struct lichao_segment_tree
{
static const ll l = -1e9, r = 1e9, inf = 1e18;
ll k;
struct line
{
ll a, b; line() {} line(ll a, ll b) : a(a), b(b) {}
ll operator() (ll x) {return a*x+b;}
};
struct node {vector<line> v; ll left = -1, right = -1;};
vector<node> v = {node()};
void q_add(ll l, ll r, line nw, ll id = 0)
{
if (v[id].v.size() < 2*k-1) {v[id].v.pb(nw); return;}
ll m = (r+l)>>1;
v[id].v.pb(nw);
nth_element(v[id].v.begin(),v[id].v.begin()+2*k-2,v[id].v.end(),[&](line a, line b) {return a(m) < b(m);});
line worst = v[id].v.back(); v[id].v.pop_back();
if (l == r) return;
ll cnt = 0;
for (line i : v[id].v)
{
bool side = worst(l) < i(l);
cnt += side; cnt -= (!side);
}
if (cnt >= 0)
{
if (v[id].left == -1) {v[id].left = v.size(); v.emplace_back();}
q_add(l, m, worst, v[id].left);
}
else
{
if (v[id].right == -1) {v[id].right = v.size(); v.emplace_back();}
q_add(m+1, r, worst, v[id].right);
}
}
void q_get(ll l, ll r, ll x, ll id, vector<ll> &ans)
{
for (line i : v[id].v) ans.pb(i(x));
if (l == r) return;
ll m = (r+l)>>1;
if (x <= m && v[id].left != -1) q_get(l,m,x,v[id].left,ans);
if (x > m && v[id].right != -1) q_get(m+1,r,x,v[id].right,ans);
}
void add(ll a, ll b) {q_add(l, r, {a, b});}
ll get(ll x)
{
vector<ll> ans; q_get(l, r, x, 0, ans);
nth_element(ans.begin(), ans.begin()+k-1, ans.end());
return ans[k-1];
}
} st;
```
- Ở code trên ta sử dụng hàm `nth_element` để tối ưu việc thêm / lấy, hàm này chạy trung bình gần tuyến tính.
- Độ phức tạp: $O(k*\log{n})$.
[Codeforces 1866K: Keen Tree Calculation](https://codeforces.com/contest/1866/problem/K)
- Đây là bài tập sử dụng tới K-th Lichao Segment Tree duy nhất mà tác giả tìm được hiện tại.
- **Tóm tắt đề bài:** Cho cây gồm $n$ đỉnh, cạnh thứ $i$ nối $u_i$ và $v_i$ có trọng số $w_i$. Trả lời $Q$ truy vấn sau:
- Cho $x, k$: mọi cạnh nối giữa $x$ với đỉnh khác có trọng số được nhân lên $k$ lần, tính độ dài đường kính cây sau khi nhân lên.
**Lưu ý:** Các truy vấn này chỉ yêu cầu tìm chứ không thay đổi thực tế trên cây.
- **Giới hạn:** $2 \leq n, Q \leq 10^5, 1 \leq u_i, v_i, x_i \leq n, 1 \leq w_i, k_i \leq 10^9.$
- **Lời giải:**
- Điều ta dễ thấy khi đọc bài toán này là những đường đi thay đổi chỉ có những đường đi qua $x$.
- Lúc này ta có thể thấy được đáp án chỉ có thể là max của đường kính ban đầu hoặc một đường đi qua $x$.
- Bây giờ bài toán sẽ trở thành tính đường đi dài nhất qua $x$.
- Thông thường nếu không thực hiện việc biến đổi các cạnh quanh $x$, ta có thể tính được đường đi dài nhất qua $x$ là tổng của $2$ đường đi dài nhất kết thúc tại $x$.
- Nói đến đây thì việc áp dụng K-th Lichao Segment Tree đã rất rõ ràng, ta chỉ cần dùng phương pháp rerooting rồi tìm $2$ đường đi tối ưu nhất qua hàm $f(k) = ed_i * k + dp_i$ với $i$ là các đỉnh kề với $x$, $dp_i$ là đường đi dài nhất của $i$ không đi qua $x$, $ed_i$ là trọng số cạnh nối $i$ và $x$.
- Code ví dụ:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define fi first
#define se second
const ll mxn = 1e5+7;
struct lichao_segment_tree
{
static const ll l_l = 1, r_r = 1e9+10, inf = 8e18;
ll k = 2;
struct line
{
ll a, b; line() {} line(ll aa, ll bb) : a(-aa), b(-bb) {}
ll operator() (ll x) {return a*x+b;}
};
struct node {vector<line> v; ll left = -1, right = -1;};
vector<node> v;
lichao_segment_tree() {v.clear(); v.emplace_back();}
void q_add(ll l, ll r, line nw, ll id = 0)
{
if ((ll)v[id].v.size() < 2*k-1) {v[id].v.pb(nw); return;}
ll m = (r+l)>>1;
v[id].v.pb(nw);
nth_element(v[id].v.begin(),v[id].v.begin()+2*k-2,v[id].v.end(),[&](line a, line b) {return a(m) < b(m);});
line worst = v[id].v.back(); v[id].v.pop_back();
if (l == r) return;
ll cnt = 0;
for (line i : v[id].v)
{
bool side = worst(l) < i(l);
cnt += side; cnt -= (!side);
}
if (cnt >= 0)
{
if (v[id].left == -1) {v[id].left = v.size(); v.emplace_back();}
q_add(l, m, worst, v[id].left);
}
else
{
if (v[id].right == -1) {v[id].right = v.size(); v.emplace_back();}
q_add(m+1, r, worst, v[id].right);
}
}
void q_get(ll l, ll r, ll x, ll id, vector<ll> &ans)
{
for (line i : v[id].v) ans.pb(i(x));
if (l == r) return;
ll m = (r+l)>>1;
if (x <= m && v[id].left != -1) q_get(l,m,x,v[id].left,ans);
if (x > m && v[id].right != -1) q_get(m+1,r,x,v[id].right,ans);
}
void add(ll a, ll b) {q_add(l_l, r_r, {a, b});}
ll get(ll x, ll kk)
{
vector<ll> ans; q_get(l_l, r_r, x, 0, ans);
if ((ll)ans.size() < kk) return 0;
nth_element(ans.begin(), ans.begin()+kk-1, ans.end());
return ans[kk-1];
}
};
ll n, qq, d[mxn], dia, ans[mxn];
bool vis[mxn];
vector<vector<pair<ll,ll>>> g(mxn), query(mxn);
vector<lichao_segment_tree> st(mxn);
vector<multiset<ll>> opt_d(mxn);
void diameter()
{
queue<ll> q; q.push(1); vis[1] = 1;
while (!q.empty())
{
ll u = q.front(); q.pop();
for (pair<ll,ll> i : g[u])
{
if (!vis[i.fi])
{
d[i.fi] = d[u]+i.se;
q.push(i.fi); vis[i.fi] = 1;
}
}
}
ll nxt = -1, mxd = -1;
for (ll i = 1; i <= n; i++)
{
if (mxd < d[i])
{
nxt = i;
mxd = d[i];
}
vis[i] = 0;
d[i] = 0;
}
q.push(nxt); vis[nxt] = 1;
while (!q.empty())
{
ll u = q.front(); q.pop();
for (pair<ll,ll> i : g[u])
{
if (!vis[i.fi])
{
d[i.fi] = d[u]+i.se;
q.push(i.fi); vis[i.fi] = 1;
}
}
}
dia = *max_element(d+1,d+n+1);
}
void dfs(ll u, ll v)
{
for (pair<ll,ll> i : g[u])
{
if (i.fi != v)
{
dfs(i.fi,u);
d[u] = max(d[i.fi]+i.se,d[u]);
st[u].add(i.se,d[i.fi]);
opt_d[u].insert(d[i.fi]+i.se);
}
}
}
void dfs2(ll u, ll v, ll ed)
{
ll erased;
if (u == 1) {for (pair<ll,ll> i : query[u]) {ans[i.se] = abs(st[u].get(i.fi,1))+abs(st[u].get(i.fi,2));}}
else
{
erased = d[u]+ed;
opt_d[v].erase(opt_d[v].lower_bound(erased));
if (opt_d[v].size() > 0)
{
st[u].add(ed,*opt_d[v].rbegin());
opt_d[u].insert(*opt_d[v].rbegin()+ed);
}
else {st[u].add(ed,0); opt_d[u].insert(ed);}
for (pair<ll,ll> i : query[u]) ans[i.se] = abs(st[u].get(i.fi,1))+abs(st[u].get(i.fi,2));
}
for (pair<ll,ll> i : g[u]) if (i.fi != v) dfs2(i.fi,u,i.se);
if (u != 1) opt_d[v].insert(erased);
st[u] = lichao_segment_tree(); opt_d[u].clear();
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (ll i = 1; i < n; i++)
{
ll a, b, c; cin >> a >> b >> c;
g[a].pb({b,c}); g[b].pb({a,c});
}
diameter(); cin >> qq;
for (ll i = 1; i <= qq; i++)
{
ll a, b; cin >> a >> b;
query[a].pb({b,i});
}
for (ll i = 1; i <= n; i++) d[i] = 0;
dfs(1,1); dfs2(1,1,0);
for (ll i = 1; i <= qq; i++) cout << max(ans[i],dia) << '\n';
}
```
## Lazy Update Trên Lichao Segment Tree
- Cho $2$ bài toán sau:
- **Đề bài $1$:** Cho mảng $A$ gồm $n$ phần tử, thực hiện $Q$ truy vấn sau online:
- Cho $l, r, a, b$, gán $A_i = \max{(A_i,a*i+b)}, \forall{i} \in [l,r]$ trong $O(\log^2{n})$.
- Cho $l, r, a, b$, thêm $a*i+b$ cho mọi phần tử $A_i, \forall{i} \in [l,r]$ trong $O(\log^2{n})$.
- Cho $i$, trả về $A_i$ trong $O(\log{n})$.
- **Đề bài $2$:** Cho mảng $A$ gồm $n$ phần tử, thực hiện $Q$ truy vấn sau online:
- Cho $l, r, a, b$, gán $A_i = \max{(A_i,a*i+b)}, \forall{i} \in [l,r]$ trong $O(\log^2{n})$.
- Cho $l, r, b$, thêm $b$ cho mọi phần tử $A_i, \forall{i} \in [l,r]$ trong $O(\log^2{n})$.
- Cho $l, r$, trả về $\max_{\forall{i} \in [l,r]}{A_i}$ trong $O(\log{n})$.
- Trước hết ta sẽ xử lí bài toán $1$. Xét query $1$ và $3$, hai query này ta có thể sử dụng Lichao Segment Tree cơ bản để xử lí, ta chỉ cần thay đổi việc thêm hàm cho mọi giá trị thành thêm hàm cho $1$ đoạn cố định.
- Về phía query $2$, khi đọc các dạng query như này, thứ ta thường nghĩ đến là Lazy Update trên Segment Tree. Thế nhưng ở bài toán này, việc thực hiện việc Lazy như bình thường sẽ không hoạt động. Vấn đề ở đây nằm ở cách chúng ta thường dùng hàm `get`, giả sử đoạn $[l,r]$ đang chứa hàm $f(x)$, nếu ta thêm vào đoạn $[l+1,r-1]$ $1$ hàm làm nó trở thành $-\infty$, nếu ta thực hiện `get` như bình thường với $1$ giá trị thuộc đoạn $[l+1,r-1]$, đáp án lúc này sẽ trả ra $f(x)$ chứ không phải $-\infty$ vì nếu cập nhật đoạn $[l+1,r-1]$, đoạn $[l,r]$ thực tế không bị ảnh hưởng, lúc này ta Walk trên Lichao Segment Tree sẽ trả ra giá trị đang nằm ở đoạn $[l,r]$ vì nó đang là giá trị tốt hơn.
- Vậy lúc này ta sẽ tránh việc giá trị được thêm sai vị trí đó như nào?
- Khi ta Lazy Update trên đoạn $[l,r]$, ta sẽ tiến hành push hàm đang ở đoạn này xuống $[l,m]$ và $[m+1,r]$ cùng lúc push hàm lazy xuống rồi xóa hẳn đoạn đó khỏi đoạn $[l,r]$, lúc này các đoạn nào không cần hàm lazy sẽ không được update, đoạn cần update sẽ chứa luôn hàm của đoạn trên và giá trị tăng của hàm lazy. Lúc này hàm `get` có thể thực hiện như cách ta thường thực hiện.
- Cài đặt:
```cpp
struct lazy_lichao_segment_tree
{
static const ll l_l = -1e9, r_r = 1e9;
struct line
{
ll a, b;
line() {a = 0; b = -1e18;}
line(ll aa, ll bb) {a = aa; b = bb;}
ll operator() (ll x) {return a*x+b;}
void add(line x) {a += x.a; b += x.b;}
};
struct node
{
line opt, lz = line(0,0);
node *right = nullptr, *left = nullptr;
void upd(line v) {opt.add(v); lz.add(v);}
};
node *root;
void push_lazy(node* &n)
{
if (n == nullptr) return;
if ((*n).left == nullptr) (*n).left = new node();
if ((*n).right == nullptr) (*n).right = new node();
(*((*n).left)).upd((*n).lz); (*((*n).right)).upd((*n).lz);
(*n).lz = line(0,0);
}
void push_line(node* &n, ll l, ll r)
{
if (n == nullptr) return;
ll m = (r+l)>>1;
insert_opt_line((*n).left, l, m, (*n).opt);
insert_opt_line((*n).right, m+1, r, (*n).opt);
(*n).opt = line();
}
void insert_opt_line(node* &n, ll l, ll r, line x)
{
if (n == nullptr) n = new node();
if ((*n).opt(l) < x(l)) swap((*n).opt,x);
if ((*n).opt(r) >= x(r)) return;
if (l == r) return;
ll m = (r+l)>>1; push_lazy(n);
if ((*n).opt(m) > x(m)) insert_opt_line((*n).right, m+1, r, x);
else {swap((*n).opt,x); insert_opt_line((*n).left, l, m, x);}
}
void insert_line(node* &n, ll l, ll r, ll u, ll v, line x)
{
if (r < u || v < l || l > r || u > v) return;
if (n == nullptr) n = new node();
if (u <= l && r <= v) return insert_opt_line(n, l, r, x);
ll m = (r+l)>>1; push_lazy(n);
insert_line((*n).left, l, m, u, v, x);
insert_line((*n).right, m+1, r, u, v, x);
}
void add_line(node* &n, ll l, ll r, ll u, ll v, line x)
{
if (r < u || v < l || l > r || u > v) return;
if (n == nullptr) n = new node();
if (u <= l && r <= v) return (*n).upd(x);
ll m = (r+l)>>1; push_lazy(n); push_line(n, l, r);
add_line((*n).left, l, m, u, v, x);
add_line((*n).right, m+1, r, u, v, x);
}
ll query(node* &n, ll l, ll r, ll x)
{
if (n == nullptr) return -(ll)1e18;
if (l == r) return (*n).opt(x);
ll ans = (*n).opt(x), m = (r+l)>>1; push_lazy(n);
if (x <= m) ans = max(ans, query((*n).left, l, m, x));
else ans = max(ans, query((*n).right, m+1, r, x));
return ans;
}
void insert(ll l, ll r, line x) {return insert_line(root, l_l, r_r, l, r, x);}
void add(ll l, ll r, line x) {return add_line(root, l_l, r_r, l, r, x);}
ll query(ll x) {return query(root, l_l, r_r, x);}
} st;
```
- Bài toán $2$ có thể thực hiện gần tương đương với bài toán $1$, tác giả sẽ không đề cập lời giải ở đây mà sẽ để lại cho độc giả tự tìm hiểu thêm về một cách cài đặt Lichao khá thú vị để thực hiện được query trên đoạn, cùng lúc có thể Lazy Update.
## Bài Tập
- Lichao Segment Tree Cơ Bản:
- [Codechef NOV17: Polynomials](https://www.codechef.com/NOV17/problems/POLY)
- [Codeforces 932F: Escape Through Leaf](https://codeforces.com/problemset/problem/932/F)
- [Codeforces 660F: Bear and Bowling 4](https://codeforces.com/problemset/problem/660/F)
- [Codeforces 311B: Cats Transport](https://codeforces.com/contest/311/problem/B)
- [Codeforces 678F: Lena and Queries](https://codeforces.com/contest/678/problem/F)
- Lazy Update Lichao Segment Tree:
- [OII Candele](https://training.olinfo.it/#/task/oii_candele/statement)
- [NOI20 Progression](https://oj.uz/problem/view/NOI20_progression)
- [Atcoder ABC177_F](https://atcoder.jp/contests/abc177/tasks/abc177_f)
- [Codeforces 713C: Sonya and Problem Wihtout a Legend](https://codeforces.com/contest/713/problem/C)
- [IOI 2018: Meetings](https://oj.uz/problem/view/IOI18_meetings)
- [Codeforces 1137E: Train Car Selection](https://codeforces.com/contest/1137/problem/E)
- [Yosupo: Range Linear Add Range Min](https://judge.yosupo.jp/problem/range_linear_add_range_min)
## Nguồn Mở Rộng
- [Maxplus Convolution](https://codeforces.com/blog/entry/98663)
Sign in with Wallet
Connect another wallet