线段树的概念引入

线段树的作用

对于区间（或者线段）的修改、维护，从O(N)的时间复杂度变成O（logN）。一个很好的优化型数据结构

线段树的描述

线段树是一种二叉树，我们用这个二叉树去表示一个线段，例如：

undefined image.png image.png

线段树的创建

线段树的核心性质：

节点i的权值=她的左儿子权值+她的右儿子权值

线段树的创建代码

tree[i].sum=tree[i\*2].sum+tree[i\*2+1].sum;

1
2
3
4
5
6
7
8
9
10
11
inline void build(int i,int l,int r){//递归建树
    tree[i].l=l;tree[i].r=r;
    if(l==r){//如果这个节点是叶子节点
        tree[i].sum=input[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(i*2,l,mid);//分别构造左子树和右子树
    build(i*2+1,mid+1,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//刚才我们发现的性质return ;
}

简单（无pushdown）的线段树

简单线段树的单点修改操作描述

过程文字描述：

首先确定要改数值在左子树还是右子树，找到后修改数值，然后按原路回溯更新每层父节点数值。

undefined

简单线段树的单点修改操作代码

1
2
3
4
5
6
7
8
9
10
inline void add(int i,int dis,int k){
    if(tree[i].l==tree[i].r){//如果是叶子节点，那么说明找到了
        tree[i].sum+=k;
        return ;
    }
    if(dis<=tree[i*2].r)  add(i*2,dis,k);//在哪往哪跑
    else  add(i*2+1,dis,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//返回更新
    return ;
}

简单线段树的区间查询操作描述

过程的文字描述：

然后我们要求13的和，我们先从根节点开始查询，发现她的左儿子12这个区间和答案区间1~3有交集，那么我们跑到左儿子这个区间。

然后，我们发现这个区间12被完全包括在答案区间13这个区间里面，那就把她的值3返回。

我们回到了14区间，发现她的右儿子34区间和答案区间13有交集，那么我们走到34区间

到了34区间，我们发现她并没有完全包含在答案区间13里面，但发现她的左儿子33区间和13区间又交集，那么久走到3~3区间

到了3~3区间，发现其被答案区间完全包含，就返回她的值3一直到最开始

33区间的3+12区间的3=6，我们知道了1~3区间和为6.

我们总结一下，线段树的查询方法：

1、如果这个区间被完全包括在目标区间里面，直接返回这个区间的值

2、如果这个区间的左儿子和目标区间有交集，那么搜索左儿子

3、如果这个区间的右儿子和目标区间有交集，那么搜索右儿子

简单线段树的区间查询操作代码

1
2
3
4
5
6
7
8
9
inline int search(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r)//如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  return 0;//如果这个区间和目标区间毫不相干，返回0
    int s=0;
    if(tree[i*2].r>=l)  s+=search(i*2,l,r);//如果这个区间的左儿子和目标区间又交集，那么搜索左儿子
    if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);//如果这个区间的右儿子和目标区间又交集，那么搜索右儿子
    return s;
}

简单线段树区间修改查询操作描述

即按区间查找的方法，将沿途全部修改

简单线段树区间修改操作代码

1
2
3
4
5
6
7
8
9
10
inline void add(int i,int l,int r,int k){
    if(tree[i].l>=l && tree[i].r<=r){//如果这个区间被完全包括在目标区间里面，讲这个区间标记k
        tree[i].sum+=k;
        return ;
    }
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
}

简单线段树单点查询操作描述

默认起始节点为根节点的区间查询，把沿途全部加起来即可

简单线段树单点查询操作描述

1
2
3
4
5
6
7
8
9
void search(int i,int dis){
    ans+=tree[i].num;//一路加起来
    if(tree[i].l==tree[i].r)
        return ;
    if(dis<=tree[i*2].r)
        search(i*2,dis);
    if(dis>=tree[i*2+1].l)
        search(i*2+1,dis);
}