线段树(模板)

题目: P3372 【模板】线段树 1

线段树:存线段
除建树外,其余操作的复杂度大部分都为O(lgn)
建一个叶子,首先要访问这个叶子,访问一个叶子的复杂度为O(lgn)
所以建n个叶子的复杂度为O(nlgn)
所以建树的复杂度为O(nlgn)

相对于差分,线段树可以边修改边查询
二叉树的性质可以简单推导,不用记
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
int n,m;
int a[N];
int lazy[N<<2];  //懒标记 
ll tree[N<<2];

void bulid(int p,int l,int r){
    if(l==r){ tree[p]=a[l];return ; }
    int mid=(l+r) >> 1;       //l加上r,再除以2 
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    tree[p]=tree[p*2]+tree[p*2+1];
}

void pushdown(int p,int len){
    lazy[p*2]+=lazy[p];
    lazy[p*2+1]+=lazy[p];
    tree[p*2]+=(len-len/2)*lazy[p];
    tree[p*2+1]+=(len>>1)*lazy[p];   
    lazy[p]=0;
} 

void add(int p,int l,int r,int x,int y,int z){
    if(x<=l&&r<=y){  //(x,y)包含(l,r),即(x,y)更大  像这样:(x (l,r) y) 
        lazy[p]+=z;
        tree[p]+=( (long long) (r-l+1) )*z;
        return ;
    }
    if(lazy[p]!=0) pushdown(p,r-l+1);
    int mid=(l+r) >> 1;
    if(x<=mid) add(p*2,l,mid,x,y,z) ;       // x<=mid 代表有左边(左子树),就进左边 
    if(y>=mid+1) add(p*2+1,mid+1,r,x,y,z);  // y>mid 代表有右边(右子树),就进右边 
    tree[p]=tree[p*2]+tree[p*2+1]; 
}

ll ask(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y) return tree[p];
    if(lazy[p]!=0) pushdown(p,r-l+1);
    int mid=(l+r)>>1;
    //第一种搜索方法 
    ll res=0;
    if(x<=mid) res+=ask(p*2,l,mid,x,y);
    if(y>=mid+1) res+=ask(p*2+1,mid+1,r,x,y); 
    return res;
    /*以下是第二种搜索方法,为了方便和统一,以后线段树区间访问都用第一种 
    if(y<=mid) return find(p*2,l,mid,x,y);
    if(x>=mid+1) return find(p*2+1,mid+1,r,x,y); 
    return find(p*2,l,mid,x,mid)+find(p*2+1,mid+1,r,mid+1,y);
    */
}

int main(){
    cin >> n >> m;
    for(int i=1;i<=n;++i) cin >> a[i];
    bulid(1,1,n);
    while(m--){
        int a;
        cin >> a;
        if(a==1){
            int b,c,d;cin >> b >> c >> d;  
            add(1,1,n,b,c,d);   //第一个1表示从根(第一个点)开始搜索目标区间,然后修改,tree的一号位置表示(1,n)的状态,所以区间是1到n 
        }
        else{
            int b,c;cin >> b >> c;
            cout << ask(1,1,n,b,c) << endl;
        }
  }
  return 0; 
}
全部评论

相关推荐

07-24 13:43
门头沟学院 Java
longerluck...:我猜说的是“你真**是个天才”
投递美团等公司10个岗位
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-25 17:55
点赞 评论 收藏
分享
07-10 14:08
已编辑
江西农业大学 Java
拒绝无效加班的小学生...:期望3k吗?java这辈子有了
点赞 评论 收藏
分享
投递拓竹科技等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务