线段树(segment tree)

 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

/**************************************************************** 
 * Description: C++ implementation of segement tree
 * Author: Alex Li
 * Date: 2023-06-25 14:53:07
 * LastEditTime: 2024-01-29 22:54:01
****************************************************************/


#include <iostream>
using namespace std;

const int maxn=10001;
int n, a[maxn];

struct node{
    int l,r,lr_max;  //l,r代码区间左右端点，lrmax表示区间[l, r]的最大值
}tree[maxn*4];  //开了四倍元素的数组，有点多，应该2倍多就够

void build(int k,int l, int r){//创建线段树，k是存储下标，l,r表示区间左右
     tree[k].l=l;
     tree[k].r=r;
     if(l==r){  //叶子结点
        tree[k].lr_max=a[l];
        return;
     }
     int mid=(l+r)/2;
     build(2*k,l,mid); //k结点的左孩子编号是2*k
     build(2*k+1,mid+1,r);//k结点右孩子编号2*k+1
     tree[k].lr_max=max(tree[2*k].lr_max,tree[2*k+1].lr_max);  //结点最值是左结点和右结点中最大值 
}

void update(int k, int i,int v){ //点更新，将a[i]修改更新为v
    if(tree[k].l==tree[k].r&&tree[k].l==i){
        tree[k].lr_max=v;
        return ;
    }
     int mid=(tree[k].l+tree[k].r)/2;
     if(i<=mid)update(2*k,i,v);
     else update(2*k+1,i,v);
     tree[k].lr_max=max(tree[2*k].lr_max,tree[2*k+1].lr_max);//回归时更新最值 
}

int query(int k, int l, int r){
   if(tree[k].l==l&&tree[k].r==r)return tree[k].lr_max;  //区间相等

   int mid=(tree[k].l+tree[k].r)/2;
   if(r<=mid)
        return query(2*k,l,r);   //左子树查询
    else if(l>mid)
        return query(2*k+1,l,r);  //右子树查询
        else
        return max(query(2*k,l,mid),query(2*k+1,mid+1,r)); //左右子树分别查询
}

//广度优先，输出tree
void printBFS(int k){
    for (int k= 1; k <=4*n; k++){
        //输出结点编号、结点左边界、右边界、区间的最大值
        if(tree[k].lr_max)cout<<k<<"\t"<<tree[k].l<<"\t"<<tree[k].r<<"\t"<<tree[k].lr_max<<"\t"<<endl;
    }
    
}
//深度优先，输出tree
// void printDFS(int k){
//     if(tree[k].lr_max){
//         //输出结点编号、结点左边界、右边界、区间的最大值
//         cout<<k<<"\t"<<tree[k].l<<"\t"<<tree[k].r<<"\t"<<tree[k].lr_max<<"\t"<<endl;
//         printDFS(2*k);
//         printDFS(2*k+1);
//     }
// }

int main(){
    cin>>n;
    //输出 n个无序数字
    for (int i = 1; i <=n; i++)cin>>a[i];
    
    build(1,1,n);  //创建线段树
    cout<<query(1,3,5)<<endl;  //查询第3-5位置之间的元素的最大值
    update(1,4,10);            //更新第4个元素为10
    cout<<query(1,3,5)<<endl;  //再次查询第3-5位之间的元素最值
    printBFS(1);             //广度优先输出 tree
    //printDFS(1);             //深度优先输出 tree


}