[Daily Basic Algorithm] Line Segment Tree – Tree Array

Hits: 0

[Daily Basic Algorithm] [Line Segment Tree] – Tree Array Version

Blogger introduction

🌊 Author homepage: Suzhou Program Dabai

🌊 About the author: 🏆CSDN high-quality creator in artificial intelligence domain🥇, one of the founders of Suzhou Kaijie Intelligent Technology Co., Ltd., and currently cooperates with several new energy companies such as Foxconn and Goertek

💬If the article is helpful to you, welcome to follow, like, favorite (one-click three-link) and some subscription columns such as C#, Halcon, python+opencv, VUE, interviews with major companies, etc.

💅 If you have any questions, please send a private message, and you will reply in time when you see it
💅 Follow Suzhou Program Dabai and share fan benefits

Introduction

Line segment trees can do many things, and all line segment trees that [tree arrays] can do can be implemented. In principle, segment tree is a very simple data structure, but it is more troublesome than tree array in code. Both the line segment tree and the tree-like array maintain a sequence, but there are many operations that can be performed by the line segment tree, and there are basically no restrictions. “Staining”, “Interval Area”, “Length”, “Maximum Continuous Sum”, etc.

principle

A segment tree is a complete binary tree data structure, for each node:

struct node {
    int l, r;
    int sum;
};

The root node stores the sum of all numbers.

This structure is relatively simple, and you can open it in half every time.

For the method of dividing the interval into two segments:

[L, R]divided [L, Mid]into[Mid + 1, R]

in$Mid = \lfloor \frac{L+R}{2} \rfloor$

storage method

Similar to the heap, the array is used for storage, and the maximum length of the array will not exceed 4N.

operate

Single point modification O(logn)

Function: Modify a value in this interval and update the line segment tree.

Single-point modification is a recursive process. It only needs to modify the nodes whose information needs to be changed (nodes related to the modified nodes). For example, if we modify 5 in the above figure, we only need to modify the four nodes [1, 7]of , [5, 7], , [5, 6]and .[5]

Interval query O(logn)

Role: Query the sum of a certain interval.

The interval query is also a recursive process. For example, to find 2 ~ 5the interval of this section, we continue to recurse down until the position of this interval is completely included.

four functions

  • pushup: update current node information with child node information

  • build: initialize the segment tree on a segment

  • modify: modify operation

  • query: query operation

Case: Dynamically find the sum of continuous intervals

input format

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

The second line contains nintegers, representing the complete sequence.

Next mlines , each line contains three integers k, a, b( k = 0, representing [a, b]the sum of the subsequence; k = 1, representing the a-th number plus b).

The sequence 1starts .

output format

Output several lines of numbers, when expressed , the continuous sum k=0of the corresponding sub-sequences .[a, b]

data range

1≤n≤100000,
1≤m≤100000,
1≤a≤b≤n,

The data guarantees that the sum of all elements in the sequence is within intrange at all times.

input sample

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

Sample output

segment tree

#include <iostream> 
using namespace std;

const int N = 1e5 + 10;

int n, m;
 int w[N];     // weights

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


void push_up(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

// u is the root node 
void  build ( int u, int l, int r)  {
     if (l == r) tr[u] = {l, r, w[r]};
     else {
         // assign the initial left and right boundaries value
        tr[u] = {l, r};

        // left and right children recursively 
        int mid = l + r >> 1 ;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);

        // renew
        push_up(u);
    }
}

int query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;

    int sum = 0;

    // Determine if there is an intersection 
    int mid = tr[u].l + tr[u].r >> 1 ;
     if (mid >= l) sum = query(u << 1 , l, r);
     if (mid < r) sum += query(u << 1 | 1 , l, r);
     return sum;
}

void modify(int u, int x, int v) {
    if (tr[u].l == tr[u].r) tr[u].sum += v;
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        push_up(u);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    build(1, 1, n);

    int k, a, b;
    while (m --) {
        scanf("%d %d %d", &k, &a, &b);
        if (k == 0) printf("%d\n", query(1, a, b));
        else modify(1, a, b);
    } 

    return 0;
}

💫Click on the direct data to receive💫

​There are all kinds of learning materials, interesting and fun programming projects, and various resources that are hard to find. ​ ​

❤️Follow Suzhou program Dabai public account ❤️

👇 👇👇

You may also like...

Leave a Reply

Your email address will not be published.