线段树

· · 算法·理论

线段树

想到的第一个解法应该是差分和前缀和，但要进行多次转变，把差分数组转成前缀和数组，把前缀和数组转化成差分数组

1\le n,m\le10^5

哇，这也太慢了吧。这里就要用到线段树

线段树顾名思义，是多条线段一起组成的树

struct Node
{
    int l;//线段树的左指针
    int r;//线段树的右指针
    int sum;//条线段数值的和
}tree[4000005];

首先，利用递归和回溯建造一棵线段树

void build(int x,int l,int r)
{
    tree[x].l=l;//给左指针赋值
    tree[x].r=r;//给右指针赋值
    if(l==r)//判断是不是最后一行
    {
        tree[x].sum=a[l];//给最后一行赋值
        return;
    }
    build(2*x,l,(l+r)/2);//这条线段树的左下方的线段
    build(2*x+1,(l+r)/2+1,r); //这条线段树的右下方的线段
    tree[x].sum=tree[2*x].sum+tree[2*x+1].sum;//回溯求这条线段的值
}

接着我们就要做求值的这一部分了

void update(int x,int l,int r)
{
    if(l<=tree[x].l&&r>=tree[x].r) //判断此线段是否在规定范围之内
    {
        sum+=tree[x].sum;
        return;
    }
        //用二分往下搜索
    int mid=(tree[x].l+tree[x].r)/2;//定义这条线段的中间
    if(l<=mid)//如果要搜查的最左标记在mid的左边
    {
        update(2*x,l,r);//向左边搜索
    }
    if(r>mid)//如果要搜查的最左标记在mid的右边边
    {
        update(2*x+1,l,r);//向右边搜索
    }
}

来重点了，我们要做加数这一部分了

void add(int x,int l,int r)
{
    if(tree[x].l>=l&&tree[x].r<=r)//如果在区间内
    {
        tree[x].sum+=k*(tree[x].r-tree[x].l+1);//进行加数
        return;
    }
    int mid=(tree[x].l+tree[x].r)/2;
    if(l<=mid)
        add(x*2,l,r);
    if(r>mid)
        add(x*2+1,l,r);
    tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;//进行回溯
}

但会发现，有时加的数用不着，所以可以加一个懒标记

void add(int x,int l,int r)
{
    if(tree[x].l>=l&&tree[x].r<=r)
    {
        tree[x].sum+=k*(tree[x].r-tree[x].l+1);
        tree[x].lan+=k; //懒标记
        return;
    }
    down(x);
    int mid=(tree[x].l+tree[x].r)>>1;
    if(l<=mid)
        add(x<<1,l,r);
    if(r>mid)
        add(x<<1|1,l,r);
    tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
}

加懒标记程序

void down(int x)
{
    if(tree[x].lan==0)//如果是零就可以结束了
        return;
    tree[x<<1].sum+=(tree[x<<1].r-tree[x<<1].l+1)*tree[x].lan;//进行加数
    tree[x<<1|1].sum+=(tree[x<<1|1].r-tree[x<<1|1].l+1)*tree[x].lan;
    tree[x<<1].lan+=tree[x].lan;//加懒标记
    tree[x<<1|1].lan+=tree[x].lan;
    tree[x].lan=0;
}

剩下的就不nan了

自己编吧