lazy优化

lazy优化

关注
发信
关注(28)粉丝(399)

线段树模板（无lazy优化）

区间修改与区间查询问题

模板：

int ans;

struct node{

    int l,r,v;

    node(){v=;}

}tree[LEN*];

int arr[LEN];

//建树

void build(int l,int r,int i){    //记录 [ l , r ]上的值，当前索引为 i

    tree[i].l=l;

    tree[i].r=r;

    if(l==r){    //如果访问到了叶子节点

        tree[i].v=arr[l];    //当前值就是arr[l,r]的值

        return;

    }

    int m=(l+r)/;    //二分

    build(l,m,LS(i));    //左子树

    build(m+,r,RS(i));    //右子树

    tree[i].v=tree[LS(i)].v+tree[RS(i)].v;    //递归建树出栈后，前驱结点的值为后继结点的和

}

//区间查询

void query(int i,int l,int r){    // i 为当前树的索引，初试化调用为 1 。查询 [ l , r ]区间上的和

    if(tree[i].l>=l && tree[i].r<=r){ //如果查询区间包裹住了当前结点区间

        ans+=tree[i].v;        //直接加上这个结点的值

        return;

    }

    if(l<=tree[LS(i)].r) //查询的 l 比左子树的右端点小

        query(LS(i),l,r);    //向左递归

    if(r>=tree[RS(i)].l) //查询的 r 比右子树的左端点大

        query(RS(i),l,r);    //向右递归

}

//单点修改

void plus_i(int i,int p,int d){    //index(current) position delta

    tree[i].v+=d;        //当前结点的值更新

    if(tree[i].l==tree[i].r) //访问到了叶子节点

        return;        //退出

    if(p<=tree[LS(i)].r)    //查询的 p 比左子树的右端点小

        plus_i(LS(i), p,d);

    if(p>=tree[RS(i)].l)     //查询的 p 比右子树的左端点大

        plus_i(RS(i), p,d);

}

//区间修改

void plus_s(int i,int l,int r,int d){

    //取查询区间与结点区间的交集

    int tl=max(l,tree[i].l);

    int tr=min(r,tree[i].r);

    if(tl<=tr) tree[i].v+=d*(tr-tl+);    //如果这个交集合法，区间加

    else return;

    if(l<=tree[LS(i)].r) //查询的 l 比左子树的右端点小

        plus_s(LS(i), l,r,d);

    if(r>=tree[RS(i)].l) //查询的 r 比右子树的左端点大

        plus_s(RS(i), l,r,d);

}

注：可以把上文的结构体拆写为3个数组

测试OJ：P3372 【模板】线段树 1

测试代码：（因为无lazy优化，只有70分。我理解不了lazy优化）

#include <stdio.h>

#include <memory.h>

#include <math.h>

#include <string>

#include <vector>

#include <set>

#include <stack>

#include <queue>

#include <algorithm>

#include <map>

#define I scanf

#define OL puts

#define O printf

#define F(a,b,c) for(a=b;a<c;a++)

#define FF(a,b) for(a=0;a<b;a++)

#define FG(a,b) for(a=b-1;a>=0;a--)

#define LEN 100010

#define MAX 1<<30

#define V vector<int>

#define ll long long

#define LS(i) i<<1

#define RS(i) i<<1|1

using namespace std;

int ans;

struct node{

    int l,r,v;

    node(){v=;}

}tree[LEN*];

int arr[LEN];

//建树

void build(int l,int r,int i){    //记录 [ l , r ]上的值，当前索引为 i

    tree[i].l=l;

    tree[i].r=r;

    if(l==r){    //如果访问到了叶子节点

        tree[i].v=arr[l];    //当前值就是arr[l,r]的值

        return;

    }

    int m=(l+r)/;    //二分

    build(l,m,LS(i));    //左子树

    build(m+,r,RS(i));    //右子树

    tree[i].v=tree[LS(i)].v+tree[RS(i)].v;    //递归建树出栈后，前驱结点的值为后继结点的和

}

//区间查询

void query(int i,int l,int r){    // i 为当前树的索引，初试化调用为 1 。查询 [ l , r ]区间上的和

    if(tree[i].l>=l && tree[i].r<=r){ //如果查询区间包裹住了当前结点区间

        ans+=tree[i].v;        //直接加上这个结点的值

        return;

    }

    if(l<=tree[LS(i)].r) //查询的 l 比左子树的右端点小

        query(LS(i),l,r);    //向左递归

    if(r>=tree[RS(i)].l) //查询的 r 比右子树的左端点大

        query(RS(i),l,r);    //向右递归

}

//单点修改

void plus_i(int i,int p,int d){    //index(current) position delta

    tree[i].v+=d;        //当前结点的值更新

    if(tree[i].l==tree[i].r) //访问到了叶子节点

        return;        //退出

    if(p<=tree[LS(i)].r)    //查询的 p 比左子树的右端点小

        plus_i(LS(i), p,d);

    if(p>=tree[RS(i)].l)     //查询的 p 比右子树的左端点大

        plus_i(RS(i), p,d);

}

//区间修改

void plus_s(int i,int l,int r,int d){

    //取查询区间与结点区间的交集

    int tl=max(l,tree[i].l);

    int tr=min(r,tree[i].r);

    if(tl<=tr) tree[i].v+=d*(tr-tl+);    //如果这个交集合法，区间加

    else return;

    if(l<=tree[LS(i)].r) //查询的 l 比左子树的右端点小

        plus_s(LS(i), l,r,d);

    if(r>=tree[RS(i)].l) //查询的 r 比右子树的左端点大

        plus_s(RS(i), l,r,d);

}

int main(){

//    freopen("D:\\CbWorkspace\\ACM数据结构\\线段树\\模板1.txt","r",stdin);

    int N,M,i,t,op,x,y,k;

    I("%d%d",&N,&M);

    for(i=;i<=N;i++){

        I("%d",&arr[i]);

    }

    build(,N,);

    while(M--){

        I("%d%d%d",&op,&x,&y);

        switch(op){

            case :

                I("%d",&k);

                plus_s(,x,y,k);

                break;

            case :

                ans=;

                query(,x,y);

                O("%d\n",ans);

                break;

        }

    }

    return ;

}

区间最大最小值查询问题

OJ 链接：P1198 [JSOI2008]最大数

AC代码：

#include <stdio.h>

#include <memory.h>

#include <math.h>

#include <string>

#include <vector>

#include <set>

#include <stack>

#include <queue>

#include <algorithm>

#include <map>

#define I scanf

#define OL puts

#define O printf

#define F(a,b,c) for(a=b;a<c;a++)

#define FF(a,b) for(a=0;a<b;a++)

#define FG(a,b) for(a=b-1;a>=0;a--)

#define LEN 400010

#define MAX 1<<30

#define V vector<int>

#define ll long long

#define LS(i) i<<1

#define RS(i) i<<1|1

using namespace std;

int ans;

struct node{

    int l,r,v;

    node(){v=;}

}tree[LEN*];

//建树

void build(int l,int r,int i){    //记录 [ l , r ]上的值，当前索引为 i

    tree[i].l=l;

    tree[i].r=r;

    tree[i].v=-MAX;

    if(l==r){    //如果访问到了叶子节点

        return;

    }

    int m=(l+r)/;    //二分

    build(l,m,LS(i));    //左子树

    build(m+,r,RS(i));    //右子树

}

//区间查询

void query(int i,int l,int r){    // i 为当前树的索引，初试化调用为 1 。查询 [ l , r ]区间上的和

    if(tree[i].l>=l && tree[i].r<=r){ //如果查询区间包裹住了当前结点区间

        ans=max(ans,tree[i].v);        //取最大值

        return;

    }

    if(l<=tree[LS(i)].r) //查询的 l 比左子树的右端点小

        query(LS(i),l,r);    //向左递归

    if(r>=tree[RS(i)].l) //查询的 r 比右子树的左端点大

        query(RS(i),l,r);    //向右递归

}

//单点修改

void plus_i(int i,int p,int d){    //index(current) position delta

    tree[i].v=max(tree[i].v,d);        //取最大值

    if(tree[i].l==tree[i].r) //访问到了叶子节点

        return;        //退出

    if(p<=tree[LS(i)].r)    //查询的 p 比左子树的右端点小

        plus_i(LS(i), p,d);

    if(p>=tree[RS(i)].l)     //查询的 p 比右子树的左端点大

        plus_i(RS(i), p,d);

}

int main(){

//    freopen("D:\\CbWorkspace\\ACM数据结构\\线段树\\最大数.txt","r",stdin);

    int N,D,t=,num,pos=;

    build(,LEN,);

    char buf[];

    I("%d%d",&N,&D);

    while(N--){

        I("%s%d",buf,&num);

        if(buf[]=='A'){

            num+=t;

            num%=D;

            plus_i(,pos++,num);

        }else{

            if(num==){

                O("%d\n",t=);

                continue;

            }

            ans=-MAX;

            query(,pos-num,pos-);

            O("%d\n",t=ans);

        }

    }

    return ;

}
05-12 00:39
Powered by LMLPHP ©2024 lazy优化 0.052280