线段树基本操作——建树+单点修改+区间查询

保存：

struct tree
{
    int l,r;
    int data;
}t[N*4];

建树：

void bulid (int p,int l,int r)  //线段树建树
{
    t[p].l=l,t[p].r=r;
    if(l==r) { t[p].data=a[l];return ;}
    int mid=(l+r)/2;
    bulid(2*p,l,mid);
    bulid(2*p+1,mid+1,r);
    t[p].data=max(t[2*p].data,t[p*2+1].data);
}

单点修改：

void change(int p,int x,int v)
{
    if(t[p].l==t[p].r) { t[p].data=v;return ;}
    int mid =(t[p].l+t[p].r)/2;
    if(x<=mid) change(p*2,x,v);
    else change(2*p+1,x,v);
    t[p].data=max(t[p*2].data,t[2*p+1].data);
}

区间查询：以最简单的最大值为例

在找某一个区间的时候，会从大分解到小，最终一般都是有多个不同深度的节点返回多个区间段最大值。

根据当前节点的区间情况分为以下种种：

1.l <= pl <= pr <= r ,这中直接返回当前区间最大值。

2.pl <= l <= pr <=r,分为两种情况：

l>mid，只会递归进入右子树: 例如：区间[1,8]上找[5,8] ,此时有5>4,进入右子树[5,8];

l<=mid,两棵树都会进去，但右子树会立刻返回，比如[1,8]上找[4,8],此时有4>=4,进入右子树后，立刻有1<=5<=8<=8，此时可以直接返回。

3.l<=pl <= r<= pr ，与上述情况类似。

4.pl<=l<=r<=pr,分为两种情况：

(1) l 和 r 都小于mid或者大于mid，只会递归一颗子树。

(2) l 和 r 在mid的两侧，两颗都会递归进去，直到满足第一种情况。

int ask(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].data;
    int mid=(t[p].l+t[p].r)/2;
    int val=-(1<<30);
    if(l<=mid) val=max(val,ask(2*p,l,r));
    if(r>mid) val=max(val,ask(2*p+1,l,r));
    return val;
}

区间查询的实质就是找线段树上可以组成[l,r]这个区间的所有节点区间。

懒标记：

由来和定义：

众所周知，线段树可以支持O(logn)的时间复杂度的区间查询，但如果要进行区间修改的话会导致所有区间的在该区间内的节点的子树下的子节点的信息都要被修改，时间复杂度度为O(N).

如果之后却根本没有用到修改后的区间的信息则前面的修改操作都是浪费时间的，所以这里我们要给当前节点的区间都在修改区间内的节点都加上一个懒标记，并完成当前节点的修改，而至于该节点下的子树的修改则是留到下一次查询或者区间修改的时候将懒标记下传。

以区间增加的懒标记为例

void pushdown(int p)
{
    if(t[p].add)
    {
        t[p*2].sum+=t[p].add*(t[p*2].r-t[p*2].l+1);
         t[p*2+1].sum+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
         t[p*2].add+=t[p].add;
         t[p*2+1].add+=t[p].add;
         t[p].add=0;
    }
}