Dynamically find the maximum value of continuous intervals and + sequence intervals (quickly master the basic properties and applications of line segment trees)

Definition of line segment tree [Academic explanation]

Segment Tree is a data structure used to efficiently handle interval queries. It represents an array as a binary tree, with each node representing an interval in the array.

The root node of the line segment tree represents the range of the entire array, and each leaf node represents an individual element in the array. Each non-leaf node represents an interval, and its left child node and right child node represent the left half and right half of the interval respectively.

The main operations of the line segment tree are construction and query. The construction operation is used to construct the given array into a line segment tree, and the query operation is used to find the sum, minimum value, maximum value, etc. of the specified interval in the line segment tree.

The construction process of the line segment tree is a recursive process. Starting from the root node, the array is continuously divided into smaller intervals until each leaf node represents a separate element.

The query operation of the line segment tree is also a recursive process. Starting from the root node, according to the relationship between the query interval and the interval represented by the current node, the left child node or the right child node is recursively queried until the node containing the query interval is found or Completely disjoint nodes.

The advantage of the line segment tree is that it can complete various interval query operations within O(logn) time complexity, such as summation, minimum value, maximum value, etc. . Therefore, it is very useful in scenarios where frequent interval queries are required, such as interval updates and queries of dynamic arrays, interval statistics, etc.

Understanding of line segment tree [custom explanation]

Binary tree

The above is the official explanation. The following is my own understanding. Looking at the picture, the line segment tree is a binary tree and looks like this.

Suppose there is a node u , the left child node of u is 2 * u, and the right child node is 2 * u + 1;
However, during the algorithm operation process, we will use bitwise operators to improve efficiency, so the left son is expressed as
u<<1 The right son is represented as u<<1 | 1

Storage of binary trees

Some friends may have seen that a binary tree is a two-dimensional graphic, so it needs a two-dimensional array to store it. Actually that's not the case, look at the picture

The summarized rules are as follows, see the picture

Line Segment Tree

Given an array, we generate its segment tree, see the picture

Each node has three properties. We use a structure to record these three properties. See the figure.

The code is as follows: Note that the length of the array must be 4 * N to prevent it from exceeding the range.

struct Node{<!-- -->
    int l,r;
    int sum;
    
}tr[4*N];

sum is the property represented by the node, which represents the sum of intervals. It can also be replaced by min max and so on, depending on the meaning of the question.

Construction of line segment tree

The construction process of the line segment tree is a recursive process. Starting from the root node, the array is continuously divided into smaller intervals until each leaf node represents a separate element.

We generally set the root node to node No. 1
Assume that what we require is the sum of intervals, and the property is sum
We set up a build function, which contains 3 parameters, the root node, the left endpoint of the interval, and the right endpoint of the interval.
For detailed explanation, please see the comments

void build(int u,int l,int r)
{<!-- -->
    tr[u].l=l,tr[u].r=r; //First assign values to the left and right endpoints of the interval
    if(l==r){<!-- -->//If the left endpoint == the right endpoint, it means it is a leaf node
        tr[u].sum=w[l];//Assign values to the properties of leaf nodes
        return ;
    }
    //The following are recursive operations
    int mid=l + r>>1;//The large interval is equally divided into two
    //Subrange provides boundary value
    build(u<<1,l,mid);
    build(u<<1|1,mid + 1,r);
    push(u);//The push operation is after setting the leaf node, you need to change the above node, which will be explained later
}

Bottom-up construction features of line segment trees

The bottom-up construction feature of the line segment tree is why we use recursive methods to build the line segment tree.
Look at the code first

void push(int u){<!-- -->
    tr[u].sum=tr[u<<1].sum + tr[u<<1|1].sum;
}

Look at the picture again

Modification operation of single point of line segment tree

A add function is required, the parameters are the root node, the point is at the position of the array, and the value to be modified
code show as below

void add(int u,int x,int v){<!-- -->
    if(tr[u].l==tr[u].r){<!-- -->//When we find the child node, we can operate
        tr[u].sum + =v;
        return ;//Stop here in time, otherwise it will time out
    }
    //The next operation is similar to binary search
    //Judge whether x is in the left or right part of the interval segment,
    //Then perform a recursive search to find the leaf node
    int mid=tr[u].l + tr[u].r>>1;
    if(x<=mid) add(u<<1,x,v);
    else add(u<<1|1,x,v);
    push(u);//After completing the modification, you need to modify the value above the parent node again
}

Query operation of line segment tree [here is taking interval sum as an example]

Here we set the query function parameter to be the root node, and search the left endpoint and right endpoint of the range of the interval
First, determine whether the interval covers the interval represented by the node. If the query interval cannot cover the interval represented by the node, then the sum of the intervals of the node is not the sum of the query intervals.
Note that there is a blind spot, that is, the query interval must be within the interval represented by the root node. Many friends will ignore this point.
If not covered, discuss on a case-by-case basis and see pictures.

code show as below:

int query(int u,int l,int r){<!-- -->
    if(l<=tr[u].l & amp; & amp; tr[u].r<=r){<!-- -->
        return tr[u].sum;
    }
    int mid=tr[u].l + tr[u].r>>1;
    int sum=0;
    if(l<=mid) sum + =query(u<<1,l,r);
    if(r>=mid + 1) sum + =query(u<<1|1,l,r);
    return sum;
}

Example 1 [Dynamic sum of continuous intervals]

Title description

Given n
An array composed of numbers has two operations: one is to modify an element, and the other is to find the subarray [a,b]
Continuous sum of .

Input format
The first line contains two integers n and m, representing the number of numbers and the number of operations respectively.

The second line contains n integers, representing the complete sequence.

The next m lines, each line contains three integers k, a, b (k=0, means finding the sum of the subsequence [a, b]; k=1, means adding the a-th number to b).

The sequence starts counting from 1.

Output format
Output several rows of numbers, indicating the continuous sum of the corresponding sub-series [a,b] when k=0.

data range
1≤n≤100000
1≤m≤100000
1≤a≤b≤n
Data guarantees that at any time, the sum of all elements in the array is within the range of int.

Input example:
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8
Output sample:
11
30
35

Question analysis

Here is the interval sum, the property is sum

Code

#include
using namespace std;
const int N =1e5 + 7;
int n,m,w[N];
struct Node{<!-- -->
    int l,r;
    int sum;
    
}tr[4*N];
void push(int u){<!-- -->
    tr[u].sum=tr[u<<1].sum + tr[u<<1|1].sum;
}

void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r;
    if(l==r){
        tr[u].sum=w[l];
        return ;
    }
    int mid=l + r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid + 1,r);
    push(u);
}
void add(int u,int x,int v){
    if(tr[u].l==tr[u].r){
        tr[u].sum + =v;
        return ;
    }
    int mid=tr[u].l + tr[u].r>>1;
    if(x<=mid) add(u<<1,x,v);
    else add(u<<1|1,x,v);
    push(u);
}
int query(int u,int l,int r){<!-- -->
    if(l<=tr[u].l & amp; & amp; tr[u].r<=r){<!-- -->
        return tr[u].sum;
    }
    int mid=tr[u].l + tr[u].r>>1;
    int sum=0;
    if(l<=mid) sum + =query(u<<1,l,r);
    if(r>=mid + 1) sum + =query(u<<1|1,l,r);
    return sum;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i + + ) cin>>w[i];
    build(1,1,n);//After inputting the array, build the line segment tree in time
    while(m--){
        int k,l,r;
        cin>>k>>l>>r;
        if(k==1) add(1,l,r);
        else cout<
Example 2 [Maximum value of interval sequence]
Title description
Enter a string of numbers and give you M questions. Each time you ask, you will be given two numbers X and Y, and you will be asked to tell the maximum number in the interval from X to Y.
Input format
 The two integers N and M in the first line represent the number of numbers and the number of times to be asked;
The next line is N numbers;
Next M lines, each line has two integers X,Y
Output format
 There are M lines of output, each line outputs a number.
data range
 1≤N≤105
 1≤M≤106
 1≤X≤Y≤N
No number in the sequence exceeds 2^31?1
 Input example:
 10 2
 3 2 4 5 6 8 1 2 9 7
 1 4
 3 8
 Output sample:
 5
 8
Question analysis
Here is the maximum value, the property is max

Code
#include<iostream>
#include<climits>
using namespace std;
const int N = 1e5 + 7;
int n,m,w[N];
struct Node{<!-- -->
    int l,r;
    int m;
}tr[N*4];

void push(int u){<!-- -->
    tr[u].m=max(tr[u<<1].m,tr[u<<1|1].m);
}

void build(int u,int l,int r){<!-- -->
    tr[u].l=l,tr[u].r=r;
    if(l==r){<!-- -->
        tr[u].m=w[l];
        return ;
    }
    int mid=l + r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid + 1,r);
    push(u);
}

int query(int u,int l,int r){<!-- -->
    if(l<=tr[u].l & amp; & amp; tr[u].r<=r){<!-- -->
        return tr[u].m;
    }
    int mid=tr[u].l + tr[u].r>>1;
    int sum=INT_MIN;
    if(l<=mid) sum=max(sum,query(u<<1,l,r));
    if(r>=mid + 1) sum=max(sum,query(u<<1|1,l,r));
    return sum;
}
int main(){<!-- -->
    cin>>n>>m;
    for(int i=1;i<=n;i + + ){<!-- -->
        scanf("%d", & amp;w[i]);
    };
    build(1,1,n);
    int x,y;
    while(m--){<!-- -->
        scanf("%d %d", & amp;x, & amp;y);
        printf("%d\
",query(1,x,y));
    }
    return 0;
}