算法笔记——线段树

 线段树节点的主要参数

①左端点        ②右端点        ③维护的区间信息        ④Lazy_tag

采用递归创建线段树

①若是叶子节点（l=r），则节点的最值就是对应位置的元素值

②若是非叶子节点，则递归创建左子树和右子树

③回溯过程中，通过节点左右子树的区间信息维护该节点的区间信息（意味着除了建树每次更新都需要递归维护）

#define lson (i<<1)
#define rson (i<<1|1)
#define mid ((tr[i].l+tr[i].r)>>1)
void build(int i,int x,int y)//节点编号、左端点值、右端点值
{
    tr[i].l=x;tr[i].r=y;
    if(x==y){tr[i].sum=a[x];    return;}//注意这里a[x]易错写成a[i]
    build(lson,x,mid);//左区间长≥右区间长
    build(rson,mid+1,y);
    tr[i].sum=tr[lson].sum+tr[rson].sum;
}

在区间查询和更新中，若节点区间被查询区间覆盖，可以直接只更新当前节点的信息，再打上一个Lazy_tag，等后续节点被访问到后再下传，降低复杂度。

打上Lazy_tag的当前节点区间信息已经被更新，子树节点未被更新，访问到该节点时即使下传Lazy_tag信息即可。下传过程即为更新两个子节点区间信息并打上Lazy_tag的过程

注意：当前节点的Lazy_tag传到下层以后要删除，防止重复下传

void push_down(int i)
{
    if(!tr[i].add)    return;
    tr[lson].add+=tr[i].add;
    tr[rson].add+=tr[i].add;
    tr[lson].sum+=tr[i].add*(len-len/2);//左区间是长的那个
    tr[rson].sum+=tr[i].add*len/2;
    tr[i].add=0;
}

①若节点所在的区间被查询区间[l,r]覆盖，则返回该节点的区间信息

②判断是在左子树中还是在右子树中继续递归查询（可能两棵子树都要查询）,并下传Lazy_tag为后续可能访问到的节点做准备

③回溯时返回区间信息

int ask(int i,int x,int y)
{
    if(tr[i].l>=x && tr[i].r<=y)    return tr[i].sum;
    push_down(i);
    int ans=0;
    if(x<=mid)    ans+=ask(lson,x,y);
    if(y>mid)     ans+=ask(rson,x,y);
    return ans;    
}

①若当前节点的区间被查询区间[l,r]覆盖，则仅对该节点进行更新并做Lazy_tag，表示该节点已被更新，该节点的子节点暂不更新。

②判断是在左子树还是右子树中继续递归查询（可能两棵子树都要查询），并下传Lazy_tage为后续可能访问到的节点做准备。

③回溯时维护节点的区间信息

#define len (tr[i].r-tr[i].l+1)
void updata(int i,int x,int y,int k)
{
    if(tr[i].l>=x && tr[i].r<=y)
    {
        tr[i].sum+=len*k;
        tr[i].add+=k;
        return;
    }
    push_down(i);
    if(x<=mid)    updata(lson,x,y,k);
    if(y>mid)     updata(rson,x,y,k);
    tr[i].sum=tr[lson].sum+tr[rson].sum;
}

由线段树的性质易得，若区间长度为N，则线段树的叶子节点有N个（l==r的情况），他们只能分布在最后一层和倒数第二层。

假设最后一层的叶子结点有m个，倒数第二层的有n个，m+n=N

因为n≤N，根据二叉树的性质，除了最后一层的m个，节点总数≤2N-1

如果所有的第二层节点都有2个子节点（即无叶子节点），则m≤2n≤4N-2

然而两个等号不可能同时取到，因此开4倍空间是安全的。

更新和查询均为