The previous article mentioned that the RMQ problem can be handled using the ST table algorithm, but when online modifications are needed, the segment tree is a better choice.
As shown in the figure, it is clear that the segment tree is a binary search tree.
The points to note are as follows:
- The segment tree is stored in an array, and the array space is generally opened up to 4*n times the original array (to be precise, n is rounded up to the next power of 2 and then multiplied by 2, e.g., 5->8->16).
- In the segment tree array storage, if a node is numbered n, then its left child is numbered 2 * n (represented as n << 1), and the right child is numbered 2*n+1 (represented as n << 1 | 1).
- The root node is defined as 1.
1. Querying the Minimum Value in a Range (Point Modification)#
Template Problem: hihoCoder #1077 RMQ Problem Revisited - Segment Tree
Problem summary: Given an array A, there are two types of operations: querying the minimum value in the range from l to r, or modifying the value at index p to v.
Using the segment tree to maintain the minimum value, to change it to query the maximum value, simply replace all min with max and change inf to 0.
1. Building the Tree#
void pushup(int rt) {// Update node information, here taking the minimum value as an example, can be changed to maximum value
Tree[rt] = min(Tree[rt << 1], Tree[rt << 1|1]);
}
void Build(int l, int r, int rt) {// [l,r] represents the range, rt represents the actual stored index
if (l == r) {// Reached leaf node
Tree[rt] = A[l];
return;
}
int mid = l+r>>1;
Build(l,mid,rt << 1);// First build the left child
Build(mid+1,r,rt << 1 | 1);// Then build the right child
pushup(rt);// Update information using left and right children
}
2. Update#
When calling, the parameters are the root node index, modification position p, the value to modify to v, and the range affected by the modification (i.e., 1~n).
void Update_point(int rt, int p, int val, int l, int r) { // Point modification
if (l == r) {
Tree[rt] = val;
return;
}
int mid = (l+r) >> 1;
if (p <= mid)// If the modification position is in the left half, update the left subtree
Update_point(rt<<1, p, val, l, mid);
else Update_point(rt<<1|1, p, val, mid+1, r);// Otherwise update the right subtree
pushup(rt);// Update the current point~
}
3. Query#
The difficulty lies here, when calling, the parameters are the root node, the entire range (1 ~ n), and the range to query (x ~ y).
Note: The range to query must be passed down continuously and will not change~ When the range to query is the sub-range l ~ r, it can return directly.
int query(int rt, int l, int r,int x, int y) {// Start querying the minimum/maximum/sum from node rt, here taking the minimum as an example
if (x <= l && r <= y) {// When l ~ r is a sub-range of the range to query, return the current node's value directly
return Tree[rt];
}
int mid = l+r >> 1;
int ans = inf;// If querying the maximum, change this to 0
if (x <= mid) // If the left endpoint of the current range is less than or equal to mid, definitely query the left half
ans = min(query(rt<<1,l,mid,x,y), ans);
if (y > mid)// If the right endpoint of the current range is greater than mid, definitely query the right half
ans = min(query(rt<<1|1,mid+1,r,x,y), ans);
return ans;
}
Complete Code#
#include <iostream>
#include <algorithm>
using namespace std;
// Definition
const int maxn = 1000005;
const int inf = 0x3f3f3f;
int Tree[maxn<<2];
int A[maxn];
int n;
void pushup(int rt) {// Update node information, here taking the minimum value as an example, can be changed to maximum value
Tree[rt] = min(Tree[rt << 1], Tree[rt << 1|1]);
}
void Build(int l, int r, int rt) {// [l,r] represents the range, rt represents the actual stored index
if (l == r) {// Reached leaf node
Tree[rt] = A[l];
return;
}
int mid = l+r>>1;
Build(l,mid,rt << 1);// First build the left child
Build(mid+1,r,rt << 1 | 1);// Then build the right child
pushup(rt);// Update information using left and right children
}
void Update_point(int rt, int p, int val, int l, int r) { // Point modification
if (l == r) {
Tree[rt] = val;
return;
}
int mid = (l+r) >> 1;
if (p <= mid)// If the modification position is in the left half, update the left subtree
Update_point(rt<<1, p, val, l, mid);
else Update_point(rt<<1|1, p, val, mid+1, r);// Otherwise update the right subtree
pushup(rt);// Update the current point~
}
int query(int rt, int l, int r,int x, int y) {// Start querying the minimum/maximum/sum from node rt, here taking the minimum as an example
if (x <= l && r <= y) {// When l ~ r is a sub-range of the range to query, return the current node's value directly
return Tree[rt];
}
int mid = l+r >> 1;
int ans = inf;// If querying the maximum, change this to 0
pushdown(rt, l, r);
if (x <= mid) // If the left endpoint of the current range is less than or equal to mid, definitely query the left half
ans += query(rt<<1,l,mid,x,y);
if (y > mid)// If the right endpoint of the current range is greater than mid, definitely query the right half
ans += query(rt<<1|1,mid+1,r,x,y);
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> A[i];
}
Build(1,n,1);
int T;
cin >> T;
while(T--) {
int a, b, c;
cin >> a >> b >> c;
if (a == 1) {
Update_point(1,b,c,1,n);
} else {
int ans = query(1,1,n,b,c);
cout << ans << endl;
}
}
return 0;
}
2. Range Modification (Sum, Difference, Product, Division, etc.)#
1. Range Addition Operation#
Luogu P3372 【Template】 Segment Tree 1
The summary is: Given a sequence of numbers, you need to perform the following two operations:
- Add kk to every number in a certain range.
- Find the sum of every number in a certain range.
Great God Solution
The great god has written so detailed, why should I write this
Forget it, it's good to type it out and keep it for reference
We can use a segment tree to maintain the range sum, and for modifications, we perform range modifications~ This requires a marking array, as point modifications are actually a subproblem of range modifications.
Pushdown Operation#
To update downwards, since the lazy mark add records the impact on its child nodes, a function to pass down the influence is needed.
inline void f(int rt, int l, int r, ll k) {// Add the influence of k to the current node and update its lazy mark
Tree[rt] += k * (r-l+1);// Range sum, here maintaining the range sum, every number in the range adds k
add[rt] += k;
}
void pushdown(int rt, int l, int r) {
int mid = l+r >>1;
f(rt<<1, l, mid, add[rt]);// Update the lazy mark and its maintained value (range sum) for the left child
f(rt<<1|1, mid+1, r, add[rt]);// Update the lazy mark and its maintained value (range sum) for the right child
add[rt] = 0;// Set the current lazy mark to 0
}
Update Range#
void Update_section(int rt, int val, int l, int r, int rl, int rr) { // Range modification
if (rl <= l && r <= rr) {// ~When the current range is a sub-range of the range to modify, directly update its value and lazy mark~
f(rt, l, r, val);
return;
}
pushdown(rt, l, r);// Before the next recursion, first pass down the current node's influence, then update the current node
int mid = (l+r) >> 1;
if (rl <= mid)// If the modified range can affect the left half, update the left subtree
Update_section(rt<<1, val, l, mid, rl, rr);
if (rr > mid)
Update_section(rt<<1|1, val, mid+1, r, rl, rr);// Otherwise update the right subtree
pushup(rt);// ~Update upwards~
}
Complete Code#
#include <iostream>
#include <algorithm>
using namespace std;
// Definition
typedef long long ll;
const int maxn = 1000005;
const int inf = 0x3f3f3f;
ll add[maxn<<2];// Lazy mark, i.e., the influence on all its child nodes, excluding itself
ll Tree[maxn<<2];
ll A[maxn];
int n, T;
inline void pushup(int rt) {// Update node information upwards, i.e., use the values of the left and right children to update the current node
Tree[rt] = Tree[rt << 1]+Tree[rt << 1|1];
}
inline void f(int rt, int l, int r, ll k) {// Add the influence of k to the current node and update its lazy mark
Tree[rt] += k * (r-l+1);// Range sum, here maintaining the range sum, every number in the range adds k
add[rt] += k;
}
void pushdown(int rt, int l, int r) {
int mid = l+r >>1;
f(rt<<1, l, mid, add[rt]);// Update the lazy mark and its maintained value (range sum) for the left child
f(rt<<1|1, mid+1, r, add[rt]);// Update the lazy mark and its maintained value (range sum) for the right child
add[rt] = 0;// Set the current lazy mark to 0
}
void Build(int l, int r, int rt) {// [l,r] represents the range, rt represents the actual stored index
add[rt] = 0;
if (l == r) {// Reached leaf node
Tree[rt] = A[l];
return;
}
int mid = l+r>>1;
Build(l,mid,rt << 1);// First build the left child
Build(mid+1,r,rt << 1 | 1);// Then build the right child
pushup(rt);// Update information using left and right children
}
void Update_section(int rt, int val, int l, int r, int rl, int rr) { // Range modification
if (rl <= l && r <= rr) {// ~When the current range is a sub-range of the range to modify, directly update its value and lazy mark~
f(rt, l, r, val);
return;
}
pushdown(rt, l, r);// Before the next recursion, first pass down the current node's influence, then update the current node
int mid = (l+r) >> 1;
if (rl <= mid)// If the modified range can affect the left half, update the left subtree
Update_section(rt<<1, val, l, mid, rl, rr);
if (rr > mid)
Update_section(rt<<1|1, val, mid+1, r, rl, rr);// Otherwise update the right subtree
pushup(rt);// ~Update upwards~
}
ll query(int rt, int l, int r,int x, int y) {// Start querying the sum from node rt for the range x~y, here taking the minimum as an example
if (x <= l && r <= y) {// When l ~ r is a sub-range of the range to query, return the current node's value directly
return Tree[rt];
}
int mid = l+r >> 1;
ll ans = 0;
pushdown(rt, l, r);
if (x <= mid) // If the left endpoint of the current range is less than or equal to mid, definitely query the left half
ans += query(rt<<1,l,mid,x,y);
if (y > mid)// If the right endpoint of the current range is greater than mid, definitely query the right half
ans += query(rt<<1|1,mid+1,r,x,y);
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> T;
for(int i = 1; i <= n; i++) {
cin >> A[i];
}
Build(1,n,1);
while(T--) {
int a, l, r;
cin >> a;
if (a == 1) {
int k;
cin >> l >> r >> k;
Update_section(1, k, 1, n, l, r);
} else {
cin >> l >> r;
ll ans = query(1, 1, n, l, r);
cout << ans << endl;
}
}
return 0;
}
2. Range Addition and Multiplication Operations (More Complete)#
Luogu P3373【Template】 Segment Tree 2
Great God Solution
This problem is based on the previous one, allowing for multiplication/addition of a number to each number in a certain range, which requires two lazy mark arrays add and mul. In the lazy mark update operation, it is also important to note that if you want to update the add mark, only update add, if you want to update mul, you must also update add (add multiplied by k).
Multiply first, then add!!
Multiply first, then add!!
Multiply first, then add!!
Important things are said three times.
Changes in Pushdown Operation#
Mainly the changes in the f function.
Note that the function of f is to add the influence of the previous node ft to the current node rt and update the lazy mark of the current node ft.
inline void f(int rt, int l, int r, int ft) {// Add the influence of the previous node ft to the current node rt, updating its lazy mark
// Multiply first, then add!! Update its value
Tree[rt] = (Tree[rt] * mul[ft]) % p;
Tree[rt] = (Tree[rt] + add[ft] * (r-l+1)) % p;
// Update lazy mark, mul is updated directly (* parent node's mul)
mul[rt] = (mul[rt] * mul[ft]) % p;
// The add lazy mark should first multiply the parent's mul mark, then add the parent's add mark!!!
add[rt] = (add[rt] * mul[ft]) % p;
add[rt] = (add[rt] + add[ft]) % p;
}
void pushdown(int rt, int l, int r) {
int mid = l+r >>1;
f(rt<<1, l, mid, rt);// Update the lazy mark and its maintained value for the left child
f(rt<<1|1, mid+1, r, rt);// Update the lazy mark and its maintained value for the right child
add[rt] = 0;
mul[rt] = 1;// Current lazy mark
}
Update Operation Changes (Divided into Two Types of Updates)#
Addition Update~
void Update_section_add(int rt,int val, int l, int r, int rl, int rr) { // Range modification +val
if (rl <= l && r <= rr) {// ~When the current range is a sub-range of the range to modify, directly update its value and lazy mark~
Tree[rt] = (Tree[rt] + val * (r-l+1)) % p;// Add the influence of val to the current node and update its lazy mark
add[rt] = (add[rt] + val) % p;
return;
}
pushdown(rt, l, r);// Before the next recursion, first pass down the influence
int mid = (l+r) >> 1;
if (rl <= mid)// If the modified range can affect the left half, update the left subtree
Update_section_add(rt<<1, val, l, mid, rl, rr);
if (rr > mid)
Update_section_add(rt<<1|1, val, mid+1, r, rl, rr);// Otherwise update the right subtree
pushup(rt);// Start backtracking~ Update upwards~
}
Multiplication Update~ Multiplication will affect the lazy mark of addition!
void Update_section_mul(int rt,int val, int l, int r, int rl, int rr) { // Range modification *val
if (rl <= l && r <= rr) {// ~When the current range is a sub-range of the range to modify, directly update its value and lazy mark~
Tree[rt] = (Tree[rt] * val) % p;
mul[rt] = (mul[rt] * val) % p;
add[rt] = (add[rt] * val) % p;// Very important!!
return;
}
pushdown(rt, l, r);// Before the next recursion, first pass down the influence
int mid = (l+r) >> 1;
if (rl <= mid)// If the modified range can affect the left half, update the left subtree
Update_section_mul(rt<<1, val, l, mid, rl, rr);
if (rr > mid)
Update_section_mul(rt<<1|1, val, mid+1, r, rl, rr);// Otherwise update the right subtree
pushup(rt);// Start backtracking~ Update upwards~
}
Complete Code#
#include <iostream>
#include <algorithm>
using namespace std;
// Definition
typedef long long ll;
const int maxn = 1000005;
ll add[maxn<<2];// Lazy mark 1, i.e., the influence on all its child nodes, excluding itself
ll mul[maxn<<2];// Lazy mark 2
ll Tree[maxn<<2];
ll A[maxn];
int n, T;
ll p;
inline void pushup(int rt) {// Update node information upwards, i.e., use the values of the left and right children to update the current node
Tree[rt] = Tree[rt << 1]+Tree[rt << 1|1];
}
inline void f(int rt, int l, int r, int ft) {// Add the influence of the previous node ft to the current node rt, updating its lazy mark
// Multiply first, then add!!
Tree[rt] = (Tree[rt] * mul[ft]) % p;
Tree[rt] = (Tree[rt] + add[ft] * (r-l+1)) % p;
// mul is updated directly
mul[rt] = (mul[rt] * mul[ft]) % p;
// The add lazy mark should first multiply the parent's mul mark, then add the parent's add mark!!!
add[rt] = (add[rt] * mul[ft]) % p;
add[rt] = (add[rt] + add[ft]) % p;
}
void pushdown(int rt, int l, int r) {
int mid = l+r >>1;
f(rt<<1, l, mid, rt);// Update the lazy mark and its maintained value for the left child
f(rt<<1|1, mid+1, r, rt);// Update the lazy mark and its maintained value for the right child
add[rt] = 0;
mul[rt] = 1;// Current lazy mark
}
void Build(int l, int r, int rt) {// [l,r] represents the range, rt represents the actual stored index
add[rt] = 0;
mul[rt] = 1;
if (l == r) {// Reached leaf node
Tree[rt] = A[l];
return;
}
int mid = l+r>>1;
Build(l,mid,rt << 1);// First build the left child
Build(mid+1,r,rt << 1 | 1);// Then build the right child
pushup(rt);// Update information using left and right children
}
void Update_section_add(int rt,int val, int l, int r, int rl, int rr) { // Range modification +val
if (rl <= l && r <= rr) {// ~When the current range is a sub-range of the range to modify, directly update its value and lazy mark~
Tree[rt] = (Tree[rt] + val * (r-l+1)) % p;// Add the influence of val to the current node and update its lazy mark
add[rt] = (add[rt] + val) % p;
return;
}
pushdown(rt, l, r);// Before the next recursion, first pass down the influence
int mid = (l+r) >> 1;
if (rl <= mid)// If the modified range can affect the left half, update the left subtree
Update_section_add(rt<<1, val, l, mid, rl, rr);
if (rr > mid)
Update_section_add(rt<<1|1, val, mid+1, r, rl, rr);// Otherwise update the right subtree
pushup(rt);// Start backtracking~ Update upwards~
}
void Update_section_mul(int rt,int val, int l, int r, int rl, int rr) { // Range modification *val
if (rl <= l && r <= rr) {// ~When the current range is a sub-range of the range to modify, directly update its value and lazy mark~
Tree[rt] = (Tree[rt] * val) % p;
mul[rt] = (mul[rt] * val) % p;
add[rt] = (add[rt] * val) % p;// Very important!!
return;
}
pushdown(rt, l, r);// Before the next recursion, first pass down the influence
int mid = (l+r) >> 1;
if (rl <= mid)// If the modified range can affect the left half, update the left subtree
Update_section_mul(rt<<1, val, l, mid, rl, rr);
if (rr > mid)
Update_section_mul(rt<<1|1, val, mid+1, r, rl, rr);// Otherwise update the right subtree
pushup(rt);// Start backtracking~ Update upwards~
}
ll query(int rt, int l, int r,int x, int y) {// Start querying the sum from node rt for the range x~y, here taking the minimum as an example
if (x <= l && r <= y) {// When l ~ r is a sub-range of the range to query, return the current node's value directly
return Tree[rt];
}
int mid = l+r >> 1;
ll ans = 0;
pushdown(rt, l, r);
if (x <= mid) // If the left endpoint of the current range is less than or equal to mid, definitely query the left half
ans = (ans + query(rt<<1,l,mid,x,y)) % p;
if (y > mid)// If the right endpoint of the current range is greater than mid, definitely query the right half
ans = (ans + query(rt<<1|1,mid+1,r,x,y)) % p;
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> T >> p;
for(int i = 1; i <= n; i++) {
cin >> A[i];
}
Build(1,n,1);
while(T--) {
int a, l, r;
cin >> a;
if (a == 1) {
int k;
cin >> l >> r >> k;
Update_section_mul(1, k, 1, n, l, r);
} else if(a == 2) {
int k;
cin >> l >> r >> k;
Update_section_add(1, k, 1, n, l, r);
} else {
cin >> l >> r;
ll ans = query(1, 1, n, l, r);
cout << ans << endl;
}
}
return 0;
}
Then~ Congratulations on AC ~ Yay~!
