Suppose we now have a very For large arrays, two operations must be performed repeatedly for the numbers in the array.

1, (query) randomly select an interval in this array, and find the sum of all numbers in this interval .

2, (update) constantly randomly modify a value in this array.

Time complexity:

< span style="font-size: 15px;">enumeration:

enumeration L~ Each number of R is added up.

• query: O(n)

Find the number you want to modify and modify it directly.

• update: O(1)

If query and update are done many, many times, the O(n) of query will be stuck, so the time complexity will be very slow. So is there a way to reduce the time complexity of query to O(1)? One of the methods is as follows:

• First create an array as large as the a array.

• s[1]=a[1];s[2] =a[1]+a[2];s[3]=a[1]+a[2]+a[3];…;s[n]=a[1]+a[2]+ a[3]+…+a[n] (store the prefix sum of a in the s array)

• At this time a[L]+a[L+1]+…+a[R]=s[R]-s[L-1], the query time is complicated The degree drops to O(1).
• But if you want to modify the value of a[k], you also need to modify s[k],s[k+1 ],…,s[n], the time complexity is increased to O(n).

Prefix and:

< span style="font-size: 15px;">query: O(1)

update: O(n)

span>

• We found that when we tried our best to change the time complexity of one of the operations to O(1), the other The time complexity of an operation becomes O(n). When there are too many query and update operations, no matter which method is used, the overall time complexity will not be particularly fast.
• So, we are going to discuss a data structure called a segment tree, which can average the time complexity of these two operations At one point, the time complexity of query and update falls on O(n log n), thereby increasing the efficiency of the entire algorithm.

Line segment tree

Suppose we get the following array of length 6: span>

Before building the line segment tree, we first explain the nature of the line segment tree:

< p>1. Each node of the line segment tree represents an interval.

2, the line segment tree has a unique root node, which represents the entire statistical range, such as [1,N].

3. Each leaf node of the line segment tree represents a meta interval [x,x] of length 1.

4. For each internal node [l,r], its left child node is [l,mid], The right child node is [mid+1,r], where mid=(l+r)/2 (rounded down).

According to this array, we build the following line segment tree (the nature of the node is sum):

If we require the sum of the medians in the interval [2-5]:

If we want to change a[4] to 6:

• Find the target node modification layer by layer, and modify the parent node of the current node in turn.

The next question is: How to save this line segment tree?

• Use array storage.

If we want to take the left and right of the node node Child node (right), the method is as follows:

• left=2*node+1
• right=2*ndoe+2

Take node 5 as an example (the left child node is node 11, and the right child node is node 12):

• left₅=2*5+1=11
• right_5=2*5+2=12

Next, the code for building the tree is given:

#include

using namespace std; const int N = 1000; int a[] = {1, 3, 5, 7, 9,  11}; int size = 6; int tree[N] = {< span style="color: #800080;">0}; //The creation range is a[start]~a[end] 

void build(int a[], int tree[], int node/*Current node*/,  int start, int end){ //recursive boundary (that is, when a leaf node is encountered) 

 if (start == end){ // directly store the value in the a array

 tree[node] = a[start];} else {// divide the established interval into Two halves

 int mid = (start + end) / 2; int left = 2 * node + 1;// The subscript of the left child node

 int right = 2 * node + 2;//The subscript of the right child node// Find the value of the left child node (that is, starting from the node left, the establishment range is a[ start]~a[mid])

 build(a, tree, left, start, mid); //Find the value of the right child node (that is, starting from the node right, the establishment range is a[start]~a[mid])

 build(a, tree, right, mid+1, end);  //The value of the left child node of the current node’s position plus the value of the right child node

 tree[node] = tree[left] + tree[right];}} int  main(){ //Start from the root node (ie node 0) to build a tree, and the tree build range is a[0]~a[size-1]

 build(a, tree, 0, 0, size-1); for (int i = 0; i <= 14; i ++) printf("tree[%d] = %d
", i, tree[i]); return 0 ; }

Run results:< /span>

update operation:

• Determine the branch that needs to be changed, look down for the node that needs to be modified, and then modify the value of the node upwards.
• Compared with the tree-building function, the update function adds two parameters x and val, which means changing a[x] to val.

Example: Change a[x] to 6 (code implementation)

void update(int a[], int tree[], int node, int start, int end, int x, int val){ //Find a[x], modify the value

 if (start == end){ a[x] =< span style="color: #000000;"> val; tree[node] = val;} else {int mid = (start + end) / 2; int left = 2 * node + 1; int right = 2 * node + 2; if (x> = start && x <= mid) {//if x is on the left branch

 update(a, tree, start, mid, x, val);} else< /span> {//If x is on the right branch

 update(a, tree, right, mid+1, end, x, val); } //Updating the value

 tree[node] = tree[left] + tree[right];}} Called in the main function: //Change a[x] to 6

update(a, tree, 0, 0, size-1, 4, 6);

Run result:

query operation:

• Find the intervals contained in the target interval in turn, and accumulate them .
• Compared with the tree-building function, the query function adds two parameters L, Rl, that is, the sum of the interval [L, R] of a.

Example: Find the value of a[2]+a[3]+…+a[5] (code implementation)

int query(int a[], int tree[], int node, int start, int end, int L,int R){ //If the target interval does not overlap with the current interval, return 0 when the recursion ends 

 if (start> R || end < L){ return 0;}  //If the target interval includes the current interval, return the node value directly

 else if (L <=start && end <= R){ return tree[node]; } else {int mid = (start + end) / 2; int left = 2 * node + 1 ; int right = 2 * node + 2; //Calculate the value of the left interval

 int sum_left = query(a, tree, left, start, mid, L, R ); //Calculate the value of the right interval

 int sum_right = query(a, tree, right, mid+1< span style="color: #000000;">, end, L, R); //Add is the answer

 return sum_left + sum_right;}} Call in the main function: < span style="color: #008000;">//Find the sum of the interval [2,5]

int ans = query(a, tree, 0, 0, size-1, 2 span>, 5); printf("ans = %d", ans);  span>

Run results:

Finally, present the complete code:

#include

using namespace std; const int N = 1000; int a[] = {1, 3, 5, 7, 9,  11}; int size = 6; int tree[N] = {< span style="color: #800080;">0}; //The creation range is a[start]~a[end] 

void build(int a[], int tree[], int node/*Current node*/,  int start, int end){ //recursive boundary (that is, when a leaf node is encountered) 

 if (start == end) {// directly store the value in the a array

 tree[node] = a[start];} else {// divide the established interval into Two halves

 int mid = (start + end) / 2; int left = 2 * node + 1;// The subscript of the left child node

 int right = 2 * node + 2;//The subscript of the right child node// Find the value of the left child node (that is, starting from the node left, the establishment range is a[ start]~a[mid])

 build(a, tree, left, start, mid); //Find the value of the right child node (that is, starting from the node right, the establishment range is a[start]~a[mid])

 build(a, tree, right, mid+1, end);  //The value of the left child node of the current node’s position plus the value of the right child node

 tree[node] = tree[left] + tree[right];}} void  update(int a[], int tree[], int node, int start, int< /span> end, int x, int val){ //Find a[x], modify the value span>

 if (start == end){ a[x] =< span style="color: #000000;"> val; tree[node] = val;} else {int mid = (start + end) / 2; int left = 2 * node + 1; int right = 2 * node + 2; if (x> = start && x <= mid) {//if x is on the left branch

 update(a, tree, left, start, mid, x, val);}  else {//if x is on the right branch

 update(a, tree, right, mid+1, end, x, val); } //Updating the value

 tree[node] = tree[left] + tree[right];}} / /Find the interval sum of a[L]~a[R]

int query(int a[], int tree[], int node, int start, int end, int L,int R){ //If the target interval does not overlap with the current interval, return 0 when the recursion ends 

 if (start> R || end < L){ return 0;}  //If the target interval includes the current interval, return the node value directly

 else if (L <=start && end <= R){ return tree[node]; } else {int mid = (start + end) / 2; int left = 2 * node + 1 ; int right = 2 * node + 2; //Calculate the value of the left interval

 int sum_left = query(a, tree, left, start, mid, L, R ); //Calculate the value of the right interval

 int sum_right = query(a, tree, right, mid+1< span style="color: #000000;">, end, L, R); //Add is the answer

 return sum_left + sum_right;}} int main(){ //Start from the root node (ie node 0) to build a tree, and the tree build range is a[0]~a[size-1]

 build(a, tree, 0, 0, size-1); for (int i = 0; i <= 14; i ++) printf("tree[%d] = %d
", i, tree[i]); printf("
< /span>");  //change a[x] to 6

 update(a, tree, 0, 0, size-1, 4, 6); for(int  i = 0; i <= 14; i ++) printf("tree[%d ] = %d
", i, tree[i]); printf( "
"); //Find the sum of the interval [2,5]

 int ans = query(a, tree, 0, 0, size-1, 2 span>, 5); printf("ans = %d", ans); return 0; }

Run result:

Learning video link

#include

using namespace std; const int N = 1000; int a[] = {1, 3, 5, 7, 9,  11}; int size = 6; int tree[N] = {< span style="color: #800080;">0}; //The creation range is a[start]~a[end] 

void build(int a[], int tree[], int node/*Current node*/,  int start, int end){ //recursive boundary (ie when a leaf node is encountered) 

 if (start == end){ // directly store the value in the a array

 tree[node] = a[start];} else {// divide the established interval into Two halves

 int mid = (start + end) / 2; int left  = 2 * node + 1;//左子节点的下标

        int right = 2 * node + 2;//右子节点的下标 //求出左子节点的值(即从节点left开始,建立范围为a[start]~a[mid])

 build(a, tree, left, start, mid); //求出右子节点的值(即从节点right开始,建立范围为a[start]~a[mid])

        build(a, tree, right, mid+1, end); //当前节点的职位左子节点的值加上右子节点的值 

        tree[node] = tree[left] + tree[right]; } } int main(){ //从根节点(即节点0)开始建树,建树范围为a[0]~a[size-1]

    build(a, tree, 0, 0, size-1); for(int i = 0; i <= 14; i ++) printf("tree[%d] = %d
", i, tree[i]); return 0; }

void update(int a[], int tree[], int node, int start, int end, int x, int val){ //找到a[x],修改值 

    if (start == end){ a[x] = val; tree[node] = val; } else { int mid = (start + end) / 2; int left  = 2 * node + 1; int right = 2 * node + 2; if (x >= start && x <= mid) {//如果x在左分支 

 update(a, tree, start, mid, x, val); } else {//如果x在右分支 

            update(a, tree, right, mid+1, end, x, val); } //向上更新值 

        tree[node] = tree[left] + tree[right]; } } 在主函数中调用： //把a[x]改成6

update(a, tree, 0, 0, size-1, 4, 6);

int query(int a[], int tree[], int node, int start, int end, int L,int R){ //若目标区间与当时区间没有重叠,结束递归返回0 

    if (start > R || end < L){ return 0; } //若目标区间包含当时区间,直接返回节点值 

    else if (L <=start && end <= R){ return tree[node]; } else { int mid = (start + end) / 2; int left  = 2 * node + 1; int right = 2 * node + 2; //计算左边区间的值 

        int sum_left  = query(a, tree, left, start, mid, L, R); //计算右边区间的值 

        int sum_right = query(a, tree, right, mid+1, end, L, R); //相加即为答案 

        return sum_left + sum_right; } } 在主函数中调用： //求区间[2,5]的和

int ans = query(a, tree, 0, 0, size-1, 2, 5); printf("ans = %d", ans); 

#include

using namespace std; const int N = 1000; int a[] = {1, 3, 5, 7, 9, 11}; int size = 6; int tree[N] = {0}; //建立范围为a[start]~a[end] 

void build(int a[], int tree[], int node/*当前节点*/, int start, int end){ //递归边界(即遇到叶子节点时) 

    if (start == end) { //直接存储a数组中的值 

        tree[node] = a[start]; } else { //将建立的区间分成两半 

        int mid = (start + end) / 2; int left  = 2 * node + 1;//左子节点的下标 

        int right = 2 * node + 2;//右子节点的下标 //求出左子节点的值(即从节点left开始,建立范围为a[start]~a[mid])

 build(a, tree, left, start, mid); //求出右子节点的值(即从节点right开始,建立范围为a[start]~a[mid])

        build(a, tree, right, mid+1, end); //当前节点的职位左子节点的值加上右子节点的值 

        tree[node] = tree[left] + tree[right]; } } void update(int a[], int tree[], int node, int start, int end, int x, int val){ //找到a[x],修改值 

    if (start == end){ a[x] = val; tree[node] = val; } else { int mid = (start + end) / 2; int left  = 2 * node + 1; int right = 2 * node + 2; if (x >= start && x <= mid) {//如果x在左分支 

 update(a, tree, left, start, mid, x, val); } else {//如果x在右分支 

            update(a, tree, right, mid+1, end, x, val); } //向上更新值 

        tree[node] = tree[left] + tree[right]; } } //求a[L]~a[R]的区间和 

int query(int a[], int tree[], int node, int start, int end, int L,int R){ //若目标区间与当时区间没有重叠,结束递归返回0 

    if (start > R || end < L){ return 0; } //若目标区间包含当时区间,直接返回节点值 

    else if (L <=start && end <= R){ return tree[node]; } else { int mid = (start + end) / 2; int left  = 2 * node + 1; int right = 2 * node + 2; //计算左边区间的值 

        int sum_left  = query(a, tree, left, start, mid, L, R); //计算右边区间的值 

        int sum_right = query(a, tree, right, mid+1, end, L, R); //相加即为答案 

        return sum_left + sum_right; } } int main(){ //从根节点(即节点0)开始建树,建树范围为a[0]~a[size-1]

    build(a, tree, 0, 0, size-1); for(int i = 0; i <= 14; i ++) printf("tree[%d] = %d
", i, tree[i]); printf("
"); //把a[x]改成6

    update(a, tree, 0, 0, size-1, 4, 6); for(int i = 0; i <= 14; i ++) printf("tree[%d] = %d
", i, tree[i]); printf("
"); //求区间[2,5]的和

    int ans = query(a, tree, 0, 0, size-1, 2, 5); printf("ans = %d", ans); return 0; }