普通线段树

普通线段树
问题引入
给定一个序列有n(n<=100000)个元素，有如下两个基本操作
查询：给定区间[l..r]，求这个区间所有元素的和
修改：修改某个元素的值。
任务：输出每个查询的值。
任务数量m(m<=100000)，只有上述两种操作。
朴素算法一
对于查询任务可以使用循环完成，时间复杂度O(n)。
对于修改任务可以直接赋值进行修改，时间复杂度O(1)。
总的时间复杂度为O(nm)，超时，无法完成任务。
朴素算法二
维护一个前缀和数组sum
对于查询任务使用sum[r]-sum[l-1]，时间复杂度O(1)。
对于修改八任务使用循环完成，时间复杂度O(n)
总的时间复杂度为O(nm)，超时，无法完成任务。
线段树

上图是区间【1-13】的线段树，每一个结点代表这个区间的和，例如[1-13]代表1-13的和它可以由其左子树[1-7]的和与右子树[8-13]区间的和之和，除叶结点每个区间都有这些性质，叶结点为给定初始数组的值。线段树有如下特点：
1.除叶结点，每个结点都有左右两个子结点，因此树高为O(logn)，n为区间长度。
2.对于结点修改，只影响logn个结点，其它结点不受影响。
3.任意一个区间，可以由不超过logn个结点构成。

一.单点修改，区间查询
1.定义结点的含义
struct node{
int l;//结点的左区间
int r;//结点的右区间
int sum;//结点的和(区间的和)
} tree[Maxn<<2];//4倍
2. int sgt[maxn<<2]
建树
节点i的权值=她的左儿子权值+她的右儿子权值。
根据这个思路，我们就可以建树了，我们设一个结构体tree，tree[i].l和tree[i].r分别表示这个点代表的线段的左右下标，tree[i].sum表示这个节点表示的线段和。
我们知道，一颗二叉树，她的左儿子和右儿子编号分别是她*2和她*2+1(根结点的编号为1)。
再根据刚才的性质，得到式子：tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;就可以建一颗线段树了！代码如下：

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 ;
}

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

1、如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
2、如果这个区间的左儿子和目标区间有交集，那么搜索左儿子
3、如果这个区间的右儿子和目标区间有交集，那么搜索右儿子
写成代码，就会变成这样：

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].rr)  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;
}

单点修改

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 ;
}

完成：P3374 【模板】树状数组 1

二、区间修改，单点查询
区间修改和单点查询，我们的思路就变为：如果把这个区间加上k，相当于把这个区间涂上一个k的标记，然后单点查询的时候，就从上跑道下，把沿路的标记加起来就好。
这里面给区间贴标记的方式与上面的区间查找类似，原则还是那三条，只不过第一条：如果这个区间被完全包括在目标区间里面，直接返回这个区间的值变为了如果这个区间如果这个区间被完全包括在目标区间里面，讲这个区间标记k。

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);
}

区间修改的单点查询

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);
}

完成：P3368 【模板】树状数组 2

三、区间修改、区间查询（核心）
当进行区间修改时，如果使用单点修改的思想，会让时间复杂度达到O(nlogn)，如何解决这个问题呢？
我们需要记录一个“懒标记”lazytage，来记录这个区间修改
区间修改（查询）的时候，我们按照如下原则：
1、如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
2、如果没有完全覆盖，则先下传懒标记
3、如果这个区间的左儿子和目标区间有交集，那么搜索左儿子
4、如果这个区间的右儿子和目标区间有交集，那么搜索右儿子
区间查询的区间修改

void add(int i,int l,int r,int k)
{
    if(tree[i].r<=r && tree[i].l>=l)//如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
    {
        tree[i].sum+=k*(tree[i].r-tree[i].l+1);
        tree[i].lz+=k;//记录lazytage
        return ;
    }
    push_down(i);//向下传递
    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);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    return ;
}

其中的pushdown，就是把自己的lazytage归零，并给自己的儿子加上，并让自己的儿子加上k*(r-l+1)

void push_down(int i)
{
    if(tree[i].lz!=0)
    {
        tree[i*2].lz+=tree[i].lz;//左右儿子分别加上父亲的lz
        tree[i*2+1].lz+=tree[i].lz;
        init mid=(tree[i].l+tree[i].r)/2;
        tree[i*2].data+=tree[i].lz*(mid-tree[i*2].l+1);//左右分别求和加起来
        tree[i*2+1].data+=tree[i].lz*(tree[i*2+1].r-mid);
        tree[i].lz=0;//父亲lz归零
    }
    return ;
}

区间修改的区间查询

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].rr)  return 0;
    push_down(i);
    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;
}

完成：P3372 【模板】线段树 1

推荐练习题
P1204 [USACOIE]挤牛奶普及-
P1276 校园外的树（增强版）普及-
P1531 I Hate It 普及/提高-
P1198 [JSOI2008]最大数 普及/提高-
P3870[TJOI2009]开关 普及/提高-
P2357守墓人 普及/提高-
P2068统计和 普及/提高-
P2846[USACO08NOV]Light Switching G 普及/提高-
P1816忠诚普及/提高-
P3353 在你窗外闪耀的星星普及/提高-
P1168中位数 普及+/提高