线段树概念：

线段树是一种二叉搜索树，其存储的是一个区间的信息，用[L，R]表示从L到R之间存在的信息。

线段树的延迟更新：

在结构体中再定义一个对象 lazy,add记录的是此节点所代表的区间所有数被加的值，在我们进行操作时，比如加减，我们就可以利用lazy然后往下修改，而不用修改一次就遍历一次，大大节约时间。

线段树的基本操作：

建树、单点查询、单点修改、区间查询、区间修改

结点的构建：

const int maxn=1e6;
struct node{
int l, r,lazy,val;
}tree[maxn<<2];//线段树要开数组的4倍

以求和为例

建树：

void build(int l,int r,int rt){
    tree[rt].lazy=0;//初始化lazy标记
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r){
        tree[rt].val=a[l];
        return;
    }
    else{
        int mid=(l+r)>>1;
        build(l,mid,rt*2);//左孩子
        build(mid,r,rt*2+1);//右孩子
        tree[rt].val=tree[rt*2].val+tree[rt*2+1].val;状态合并，此结点的为两个孩子的val和
    }
}

单点查询

int querynode(int rt){//单点查询(二分）
    if(tree[rt].l==tree[rt].r){//当前结点的左右端点相等，为叶子节点，是最终答案
        return tree[rt].val;
    }
    int mid=(tree[rt].l+tree[rt].r)>>1;
    if(rt<=mid)//目标位置比中点靠左，就递归左孩子
        querynode(rt*2);
    else//反之，递归右孩子
        querynode(rt*2+1);
}

单点修改

void updatenode(int rt,int c){
    if(tree[rt].l==tree[rt].r){//找到目标位置
        tree[rt].val+=c;
        return;
    }
    int mid=(tree[rt].l+tree[rt].r)>>1;
    if(rt<=mid)//目标位置比中点靠左，就递归左孩子
        updatenode(rt*2,c);
    else//反之，递归右孩子
        updatenode(rt*2+1,c);
    tree[rt].val=tree[rt*2].val+tree[rt*2+1].val;//所有包含结点k的结点状态更新
}

区间查询：

int query(int l,int r,int rt){//区间查询
    if(tree[rt].l>=l&&tree[rt].r<=r)
        return tree[rt].val;
    else if(l>l||r<1)
        return 0;
    else{
        return query(l,r,rt<<1)+query(l,r,rt<<1|1);
    }
}

区间修改：

为了避免超时，引用延迟标记
每次更新的时候不要更新到底，用延迟标记使得更新延迟到下次需要更新 or 询问的时候。下次更新或者查询的时候，如果查到该节点，就把延迟标记进行下传，将值加到他的子节点上去，同时将延迟标记变为 0，避免下次重复更新。这样只更新到查询的子区间，不需要再往下找了，极大的降低了时间复杂度。

下推：

void pushdown(int rt){//下推
    tree[rt*2].lazy+=tree[rt].lazy;//左孩子更新延迟标记
    tree[rt*2+1].lazy+=tree[rt].lazy;//右孩子更新延迟标记
    tree[rt*2].val+=tree[rt].lazy*(tree[rt*2].r-tree[rt*2].l+1);//左孩子状态更新
    tree[rt*2+1].val+=tree[rt].lazy*(tree[rt*2+1].r-tree[rt*2+1].l+1);//右孩子状态更新
    tree[rt].lazy=0;//清除本结点标记
}

区间修改：

void updata(int l,int r,int rt,int c){//区间更新
    if(tree[rt].l>=l&&tree[rt].r<=r){
        tree[rt].val+=c*(tree[rt].r-tree[rt].l+1);
        tree[rt].lazy+=c;
        return;
    }
    pushdown(rt);
    updata(l,r,rt*2,c);
    updata(l,r,rt*2+1,c);
    tree[rt].val=tree[rt*2].val+tree[rt*2+1].val;

}

明天整理题目