数据结构

线段树

Posted by Liao on 2019-09-13

1.定义

线段树（segment tree） 是用来存放给定区间内对应信息的一种数据结构。线段树是二叉树，一个区间每次被折半往下分，所以往下查找，（二叉树的二分查找）最多lon2n次就能查找到。

有两种操作：

​ 1）求某段区间的和

​ 2）修改某个区间的值

2.过程

1）建立二叉树

​

2）剪枝部分 e.g.求区间[2,5]的和

  • 可以直接返回 return0，即不用对其以下的结点进行

​ start > R || end < L

​

​

  • 本可以分成[0,1,2] [3,4,5]，求出结点2的值，以及区间[3,4,5]的和即可， 按照递归的求法，会继续搜索到结点11,12,6(start == end，即叶子结点)，多出很多无用的查找。因此可以通过判断[start,end]在[L,R] 区间内就即可，超过[L,R]的点便可不用查找。

start>=L && end<=R

​

3.模板

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#define MAX_LEN 1000  //结点个数

//建立二叉树
void build_tree(int arr[],int tree[],int node,int start,int end)
{
    if(start == end)   //递归出口 当开始等于结尾时，相当于已经找到该结点
    {
        tree[node] = arr[start];  // tree[node] = arr[end]也可
    }
    else
    {
        int mid = (start+end)/2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;
		//二分法 递归建树
        build_tree(arr,tree,left_node,start,mid);
        build_tree(arr,tree,right_node,mid+1,end);
        tree[node] = tree[left_node] + tree[right_node];
    }

}

//更新某个值
void update_tree(int arr[],int tree[],int node,int start,int end,int idx,int val)
{
    if(start == end)  //递归找到子节点后开始返回
    {
        arr[idx] = val;
        tree[node] = val;
    }
    else   //递归寻找要更新的点
    {
        int mid = (start+end)/2;
        int left_node = 2 * node+1;
        int right_node = 2 * node +2;
        if(idx>=start && idx<=mid)  //要修改的点在左子树
        {
            update_tree(arr,tree,left_node,start,mid,idx,val);
        }
        else
        {
            update_tree(arr,tree,right_node,mid+1,end,idx,val);
        }
        tree[node] = tree[left_node]+tree[right_node];
    }
}


int query_tree(int arr[],int tree[],int node,int start,int end,int L,int R)  //需要剪枝
{
    if(R<start  || L>end)
        return 0;
    else if(L<=start && end<=R)
        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 sum_left = query_tree(arr,tree,left_node,start,mid,L,R);
        int sum_right = query_tree(arr,tree,right_node,mid+1,end,L,R);
    }

    return sum_left+sum_right;
}
int main()
{
    int arr[] = {1,3,5,7,9,11};
    int size = 6;
    int tree[MAX_LEN] = {0};

    build_tree(arr,tree,0,0,size-1);
    for(int i=0;i<15;i++)
    {
        printf("tree[%d] = %d\n",i,tree[i]);
    }

    printf("\n");
    update_tree(arr,tree,0,0,size-1,4,6);
    for(int i=0;i<15;i++)
    {
        printf("tree[%d] = %d\n",i,tree[i]);
    }

    int ans = query_tree(arr,tree,0,0,size-1,2,5);
    printf("arr[2]~arr[5]的和为%d\n",ans);
    return 0;
}

FEATURED TAGS
数据结构
FRIENDS