SegmentTree

线段树

一、简介

线段树是一种树形数据结构，用于维护区间信息
线段树的每一个节点表示一段区间，根节点表示整个区间，而叶节点表示区间的一个点

线段树可以高效地完成区间查询、区间修改等操作，时间复杂度为O(logn)

二、操作

(1)建树 build
(2)自下而上更新 pushup
(3)自上而下更新 pushdown
(4)修改 modify
(5)查询 query

(1)建树
给定一段区间，建立起一棵线段树

1
2
3
4
5
6
7
8
9
10
void build(int u,int l,int r){//u-当前节点 l当前左端点 r当前右端点
    tr[u]={l,r};//存储当前点表示的区间
    if(l==r) return;//如果是叶子节点则不需要向下建树
    
    int mid=(l+r)/2;
    build(u*2,l,mid);//建立左子树
    build(u*2+1,mid+1,r);//建立右子树
}

build(1,1,n);

(2)自下而上更新
由子节点推导出父节点的值

1
2
3
4
void pushup(int u){
    //由子节点的最大值推导父节点的最大值
    tr[u].v=max(tr[u*2].v , tr[u*2+1].v);
}

(4)修改
1.单点修改

1
2
3
4
5
6
7
8
9
10
//u-当前节点 k-待修改节点的编号 x-待修改的值
void modify(int u,int k,int x){
    if(tr[u].l==k&&tr[u].r==k) tr[u].v=x;//找到了待修改节点，直接修改
    else{
        int mid=(tr[u].l+tr[u].r)/2;
        if(k<=mid) modify(u*2,k,x);//如果待修改节点在区间左半部分，在左半部分查找
        else modify(u*2+1,k,x);//在右半部分查找
        pushup(u);//自下而上更新每个节点
    }
}

2.区间修改

(5)查询

1
2
3
4
5
6
7
8
9
10
11
int query(int u,int l,int r){
    //如果待查询区间完全包含节点u的区间，则直接返回当前节点的值，不需要往下递归
    if(l<=t[u].l&&r>=t[u].r) return t[u].v;
    
    int mid=(t[u].l+t[u].r)/2;
    
    int res=0;
    if(l<=mid) res=query(u*2,l,r);//如果待查询区间与当前区间的左半部分有交集
    if(r>mid) res=max(res,query(u*2+1,l,r));//右半部分有交集
    return res;
}