线段树（重新学习）

这已经是我第三次学习线段树了

第一次学习线段树，是懵逼状态，第二次复习线段树，小有理解，这次也不知道会怎么样，但是还是准备再学习一下线段树，而且之前写的线段树讲解很粗糙

为什么要学习线段树

比如​

​1---1e7​

​这个区间，我想知道这个区间的和，用for循环可以写:

for(int i=1;i<=1e7;i++)
sum+=a[i];
注意:每一个点的值是随机的,1--1e7并不呈线性
这样求解的效率十分的低,每当我想知道一个大区间的和的时候
就需要循环很多次,这样O(n)的时间复杂度是无法满足要求的      

线段树的时间复杂度是​

​log(n)​

​,效率十分高

线段树

线段树可以说是一个二叉树，基于二分的思想写的，将大区间不断分下去，最后一个大区间变成多个点，每一个节点代表它再分下去的两个区间的（信息所进行的操作,比如两个节点相加）

接下来开始绘一个8个节点的线段树图:

在建图的过程中我们可以得到上图中包含的所有区间的信息

举个栗子：

我们要求图上所有区间的和

1-->8区间的和:36
5-->8区间的和:26
7-->8区间的和:15
5-->6区间的和:11
1-->4区间的和:10
8-->8区间的和:8
3-->4区间的和:7
7-->7区间的和:7
6-->6区间的和:6
5-->5区间的和:5
4-->4区间的和:4
1-->2区间的和:3
3-->3区间的和:3
2-->2区间的和:2
1-->1区间的和:1      

如何建图:

写一个结构体,存储节点的信息
#define maxn 1005
struct settree
{
    int l,r;//区间端点
    int sum;//区间和
    
}tree_p[4*maxn+5];      

void update(int k)//区间维护,记录节点信息
{
    tree_p[k].sum=tree_p[k*2].sum+tree_p[k*2+1].sum;
    //当前节点的和为其左右子节点的和
}      

建图：

void set_tree(int k,int l,int r)
{
    tree_p[k].l=l;//记录该节点的区间
    tree_p[k].r=r;
    if(l==r)//当区间缩为点时，赋值即可
    {
        tree_p[k].sum=w[l];
        return ;
    }
    int mid=(l+r)/2;
    set_tree(k*2,l,mid);//左子叶
    set_tree(k*2+1,mid+1,r);//右子叶
    update(k);//回溯的时候维护节点的信息
}      

建完图之后，就该询问区间的信息了，现在将区间查询，我把这个图再拿下来，再观察一下有什么问题

在建树的时候我说了，图中包含的区间 。呢么图中当然有一些区间并没有包含。例如:[3,6]区间，[2,3]区间等。我们要知道这些区间的信息，可以通过合并几个区间去得到答案

int query_ans(int k,int l,int r)
{
    if(tree_p[k].l>=l&&tree_p[k].r<=r)//在区间内
    {
        return tree_p[k].sum;
    }
    int mid=(tree_p[k].l+tree_p[k].r)>>1;
    if(mid>=r)//说明我们要求的区间,在节点k的左区间
    {
        return query_ans(k*2,l,r);
    }
    if(mid<l)
    {
        return query_ans(k*2+1,l,r);//说明在节点k的右区间
    }
    return query_ans(k*2,l,r)+query_ans(k*2+1,l,r);
}      

接下来讲单点修改，所谓牵一发而动全身，改一点而动全局，通过要修改的点​

​x​

​​，寻找x点，更改x点的值，然后回溯到节点​

​1​

​​，在回溯的过程中更改每一个节点的​

​sum​

​

void point_chan(int k,int x,int y)//单点修改
{
    if(tree_p[k].l==tree_p[k].r)
    {
        tree_p[k].sum=y;
        return ;
    }
    int mid=(tree_p[k].l+tree_p[k].r)>>1;
    if(mid>=x)//通过比较每一个节点的mid判断x的在该节点的那一边
    {
        point_chan(k*2,x,y);
    }
    else
    {
        point_chan(k*2+1,x,y);
    }
    update(k);
}      

区间修改和区间查询

对于区间修改，我们如果按照单点一个一个修改，呢么效率会很低，时间复杂度为​

​O(nlogn)​

​​,这里引入懒人标记​

​lazy​

​​,来高效的进行​

​O(logn)​

​更高效的操作

void push_down(int k)//下传懒人标记
{
    if(tree[k].l==tree[k].r)//如果没有叶子节点就不下传
    {
        tree[k].lazy=0;
        return;
    }
    if(tree[k].lazy)//开始下传
    {
        tree[k<<1].sum+=(tree[k<<1].r-tree[k<<1].l+1)*tree[k].lazy;
        tree[k<<1|1].sum+=(tree[k<<1|1].r-tree[k<<1|1].l+1)*tree[k].lazy;
        tree[k<<1].lazy+=tree[k].lazy;
        tree[k<<1|1].lazy+=tree[k].lazy;
        tree[k].lazy=0;
    }
}      

void setment(int k,int l,int r,int x)
{
    if(tree[k].l==l&&tree[k].r==r)//在回溯过程中完成操作
    {

        tree[k].sum+=(r-l+1)*x;
        tree[k].lazy+=x;
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(mid>=r)
    {
        setment(k<<1,l,r,x);
    }
    else if(mid<l)
    {
        setment(k<<1|1,l,r,x);
    }
    else
    {
        setment(k<<1,l,mid,x);
        setment(k<<1|1,mid+1,r,x);
    }
    push_up(k);
}      

int query_ans(int k,int l,int r)//修改区间和单点不一样
{
    if(tree[k].lazy)
        push_down(k);
    if(tree[k].l>=l&&tree[k].r<=r)
    {
        return tree[k].sum;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(mid>=r)
    {
        return query_ans(k<<1,l,r);
    }
    else if(l>mid)
    {
        return query_ans(k<<1|1,l,r);
    }
    return query_ans(k<<1,l,mid)+query_ans(k<<1|1,mid+1,r);
}      

完整的区间更改代码：

#include<bits/stdc++.h>
using namespace std;
//线段树区间更新,区间查询
#define maxn 1005
struct node
{
    int sum,l,r,lazy;//区间求和
} tree[maxn];
int w[maxn];
void push_up(int k)//区间维护
{
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
void push_down(int k)//下传懒人标记
{
    if(tree[k].l==tree[k].r)
    {
        tree[k].lazy=0;
        return;
    }
    if(tree[k].lazy)
    {
        tree[k<<1].sum+=(tree[k<<1].r-tree[k<<1].l+1)*tree[k].lazy;
        tree[k<<1|1].sum+=(tree[k<<1|1].r-tree[k<<1|1].l+1)*tree[k].lazy;
        tree[k<<1].lazy+=tree[k].lazy;
        tree[k<<1|1].lazy+=tree[k].lazy;
        tree[k].lazy=0;
    }
}
void set_tree(int k,int l,int r)
{
    tree[k].l=l;
    tree[k].r=r;
    if(l==r)
    {
        tree[k].sum=w[l];
        return;
    }
    int mid=(l+r)>>1;
    set_tree(k<<1,l,mid);
    set_tree(k<<1|1,mid+1,r);
    push_up(k);//区间维护
}
void setment(int k,int l,int r,int x)
{
    if(tree[k].l==l&&tree[k].r==r)//在回溯过程中完成操作
    {

        tree[k].sum+=(r-l+1)*x;
        tree[k].lazy+=x;
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(mid>=r)
    {
        setment(k<<1,l,r,x);
    }
    else if(mid<l)
    {
        setment(k<<1|1,l,r,x);
    }
    else
    {
        setment(k<<1,l,mid,x);
        setment(k<<1|1,mid+1,r,x);
    }
    push_up(k);
}
int query_ans(int k,int l,int r)//修改区间和单点不一样
{
    if(tree[k].lazy)
        push_down(k);
    if(tree[k].l>=l&&tree[k].r<=r)
    {
        return tree[k].sum;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(mid>=r)
    {
        return query_ans(k<<1,l,r);
    }
    else if(l>mid)
    {
        return query_ans(k<<1|1,l,r);
    }
    return query_ans(k<<1,l,mid)+query_ans(k<<1|1,mid+1,r);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    set_tree(1,1,n);
    int l,r,x;
    cin>>l>>r;
    int ans=query_ans(1,l,r);
    cout<<ans<<endl;
    cin>>l>>r>>x;
    setment(1,l,r,x);
    cout<<query_ans(1,l,r)<<endl;

}