线段树

一、算法描述

二、算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
/*
    参数说明：
    tree下标为node的点应该存放arr[start:end]的点的总和
*/
void build_tree(vector<int> &tree, vector<int> &arr, int node, int start, int end)
{
    if (start == end)
        tree[node] = arr[start];
    else 
    {
        int mid = (start + end) >> 1;  // mid为向下取整，所有mid值为左边区间的右端点
        int left_node = 2 * node + 1;  // node左节点在tree中的位置
        int right_node = 2 * node + 2; // node右节点在tree中的位置
        build_tree(tree, arr, left_node, start, mid);
        build_tree(tree, arr, right_node, mid + 1, end);
        tree[node] = tree[left_node] + tree[right_node];
    }
}
void update_tree(vector<int> &tree, vector<int> &arr, int node, int start, int end, int cot, int val)
{
    if (start == end && start == cot)
    {
        tree[node] = val;
        arr[cot] = val;
    }
    else
    {
        int mid = (start + end) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;
        //类似二分查找
        if (start <= cot && cot <= mid)
            update_tree(tree, arr, left_node, start, mid, cot, val);
        else
            update_tree(tree, arr, right_node, mid + 1, end, cot, val);
        tree[node] = tree[left_node] + tree[right_node]; //更新完后要记得更新一下
    }
}
int query_tree(vector<int> &tree, vector<int> &arr, int node, int start, int end, int L, int R)
{
    if (R < start || L > end)
        return 0;
    else if (L <= start && end <= R)//如果该tree是查询区间的子区间，直接取
        return tree[node];
    else if (start == end)
        return tree[node];
    else
    {
        int mid = (start + end) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;
        int left_sum = query_tree(tree, arr, left_node, start, mid, L, R);
        int right_sum = query_tree(tree, arr, right_node, mid + 1, end, L, R);
        return left_sum + right_sum;
    }
}
int main()
{
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    int len = arr.size();
    vector<int> tree(len << 2, 0); //同时初始化所有的节点为0，即记录空节点的val
}

三、参考链接

【数据结构】线段树（Segment Tree）_哔哩哔哩_bilibili