線段樹基礎合集
codevs上的一些題,是線段樹入門(裸)題,比較全面。
包括:
1080:單點修改,區間求和
1081:區間add,詢問單點值
1082:區間add,區間求和
4919:複雜一點的區間修改,區間求和
4927:區間add,區間set,區間求和
另外還有我不會的
5037
,大佬說是分塊做?
CodeVS-1080
裸地基本線段樹,當個闆子吧。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <iomanip>
#include <string>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN = ;
const int MA_XN=;
const int oo = ;
const long long int loo = l;
typedef long long int ll;
typedef struct{
int data;
int lazy;
} tree;
tree sum[MAXN<<];
void PushUP(int rt){
sum[rt].data=sum[rt<<].data+sum[rt<<|].data;}
void build (int l,int r,int rt){
if ( l == r )
{
int ttt;
scanf("%d",&ttt);
sum[rt].data=ttt;
return;
}
int m = ( l + r ) >> ;
build (lson);
build (rson);
PushUP ( rt );
}
void update(int p,int num,int l,int r,int rt)
{
if(l==r)
{
sum[rt].data+=num;
return;
}
int m=(l+r)>>;
if(p<=m)
{
update(p,num,lson);
}
if(p>m)
{
update(p,num,rson);
}
PushUP(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return sum[rt].data;
}
int m=(l+r)>>;
ll res=;
if(L<=m) res+=query(L,R,lson);
if(m<R) res+=query(L,R,rson);
return res;
}
int main ()
{
int n;
while(~scanf("%d",&n))
{
memset(sum,,sizeof(sum));
build(,n,);
int m;
scanf("%d",&m);
for(int i=;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a==)
{
//加法
update(b,c,,n,);
}
else
{
int res=query(b,c,,n,);
printf("%d\n",res);
}
}
}
return ;
}
CodeVS-1081
這題很無聊,詢問單點值。直接參考1082的代碼吧。
CodeVS-1082
基本的lazy标記使用。
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
#define M(a,b) memset(a,b,sizeof(a))
#define N n
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN=;
const int oo=;
typedef long long LL;
const LL loo=l;
typedef long double LB;
const LL mod=+;
const double eps=;
struct SegmentTree
{
LL sum;
int lazy;
}stree[*MAXN];
void pushup(int rt)
{
stree[rt].sum=stree[rt<<].sum+stree[rt<<|].sum;
}
void pushdown(int rt, int m)
{
if(stree[rt].lazy!=)
{
stree[rt<<].sum+=LL(m-(m>>))*stree[rt].lazy;
stree[rt<<|].sum+=LL(m>>)*stree[rt].lazy;
stree[rt<<].lazy+=stree[rt].lazy;
stree[rt<<|].lazy+=stree[rt].lazy;
stree[rt].lazy=;
}
}
void build(int l, int r, int rt)
{
if(l==r)
{
int tmp;scanf("%d", &tmp);
stree[rt].sum=tmp;
stree[rt].lazy=;
return;
}
int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt);
}
void update(int L, int R, int c, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
stree[rt].sum+=LL(r-l+)*c;
stree[rt].lazy+=c;
return;
}
pushdown(rt, r-l+);
int m=(l+r)>>;
if(L<=m) update(L, R, c, lson);
if(m<R) update(L, R, c, rson);
pushup(rt);
}
LL query(int L, int R, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
return stree[rt].sum;
}
pushdown(rt, r-l+);
int m=(l+r)>>;
LL res=;
if(L<=m) res+=query(L,R, lson);
if(m<R) res+=query(L, R, rson);
return res;
}
int main(int argc, char *argv[])
{
int m, n;
while(scanf("%d", &n)==)
{
build(, n, );
int m;scanf("%d", &m);
while(m--)
{
int cz;scanf("%d", &cz);
if(cz==)
{
int l, r, c;scanf("%d%d%d", &l, &r, &c);
update(l, r, c, , n, );
}
else
{
int l, r;scanf("%d%d", &l, &r);
printf("%lld\n", query(l, r, , n, ));
}
}
}
return ;
}
CodeVS-4919
複雜一點的區間修改,問多少數能被7整除。
因為涉及區間的加法,很容易想到,加法相當于shift操作。線段樹的每個點上開一個長度7的數組,記錄區間内模7餘0123456的數分别有多少個。區間加法相當于shift操作。合并直接合并左右區間對應餘數的個數即可。配合lazy使用。
另注:5037跟這題表面很像,實際這題的方法用不了。我表示無能為力。
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
#define M(a,b) memset(a,b,sizeof(a))
#define N n
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN=;
const int oo=;
typedef long long LL;
const LL loo=l;
typedef long double LB;
const LL mod=+;
const double eps=;
struct SegmentTree
{
LL sum[];
int lazy;
}stree[*MAXN];
void pushup(int rt)
{
for(int i=;i<;i++)
stree[rt].sum[i]=stree[rt<<].sum[i]+stree[rt<<|].sum[i];
}
void pushdown(int rt)
{
if(stree[rt].lazy!=)
{
int py=stree[rt].lazy;
int tmp[];
for(int i=;i<;i++) tmp[i]=stree[rt<<].sum[i];
for(int i=;i<;i++) stree[rt<<].sum[(i+py)%]=tmp[i];
for(int i=;i<;i++) tmp[i]=stree[rt<<|].sum[i];
for(int i=;i<;i++) stree[rt<<|].sum[(i+py)%]=tmp[i];
stree[rt<<].lazy+=stree[rt].lazy;
stree[rt<<|].lazy+=stree[rt].lazy;
stree[rt].lazy=;
}
}
void build(int l, int r, int rt)
{
if(l==r)
{
for(int i=;i<;i++) stree[rt].sum[i]=;
int tmp;scanf("%d", &tmp);
stree[rt].sum[tmp%]=;
stree[rt].lazy=;
return;
}
int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt);
}
void update(int L, int R, int c, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
int py=c;
int tmp[];
for(int i=;i<;i++) tmp[i]=stree[rt].sum[i];
for(int i=;i<;i++) stree[rt].sum[(i+py)%]=tmp[i];
stree[rt].lazy+=c;
return;
}
pushdown(rt);
int m=(l+r)>>;
if(L<=m) update(L, R, c, lson);
if(m<R) update(L, R, c, rson);
pushup(rt);
}
LL query(int L, int R, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
return stree[rt].sum[];
}
pushdown(rt);
int m=(l+r)>>;
LL res=;
if(L<=m) res+=query(L, R, lson);
if(m<R) res+=query(L, R, rson);
return res;
}
int main(int argc, char *argv[])
{
int m, n;
while(scanf("%d", &n)==)
{
build(, n, );
int m;scanf("%d", &m);
while(m--)
{
char cz[];scanf("%s", cz);
if(cz[]=='a')
{
int l, r, c;scanf("%d%d%d", &l, &r, &c);
update(l, r, c%, , n, );
}
else
{
int l, r;scanf("%d%d", &l, &r);
printf("%lld\n", query(l, r, , n, ));
}
}
}
return ;
}
CodeVS-4927
這題涉及兩個lazy标記的傳遞順序問題。set的優先級要高于add:比如一些數,我先add,在set,那麼add便沒用了;而我先set,在add,那麼這個add也是有用的,仍需要向下傳遞。
按我的代碼風格,每添加一個标記,立馬修改本區間的值(sum,max,min),并設定本區間lazy有效;若添加的标記是set,那麼置本區間add無效;待查詢時,要是查詢本區間,那麼不傳遞lazy,查詢子區間時經過本區間,那麼向下傳遞lazy。
向下傳遞lazy時注意:若set有效,那麼先傳遞set,并置子區間的add無效;若本區間set與add同時有效,說明本區間先set後add過,兩标記都要向下傳遞!我最開始犯了兩個錯誤:1是傳遞set後将本區間的add也置為無效了;2是傳遞完set就return了。因為我的代碼風格,set後置本區間add無效(子區間也是如此,因為向下傳遞set時置了add無效),是以addset同時出現一定是先set後add。
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
#define M(a,b) memset(a,b,sizeof(a))
#define N n
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN=;
const int oo=;
typedef long long LL;
const LL loo=l;
typedef long double LB;
const LL mod=+;
const double eps=;
struct SegmentTree
{
LL sum;
LL lazy;
LL set;
bool sset;
LL mi;
LL ma;
}stree[*MAXN];
void pushup(int rt)
{
stree[rt].sum=stree[rt<<].sum+stree[rt<<|].sum;
stree[rt].mi=min(stree[rt<<].mi, stree[rt<<|].mi);
stree[rt].ma=max(stree[rt<<].ma, stree[rt<<|].ma);
}
void pushdown(int rt, int m)
{
if(stree[rt].sset==true)
{
LL tmp=stree[rt].set;stree[rt].set=;stree[rt].sset=false;
stree[rt<<].sum=tmp*(m-(m>>));
stree[rt<<|].sum=tmp*(m>>);
stree[rt<<].ma=stree[rt<<|].ma=tmp;
stree[rt<<].mi=stree[rt<<|].mi=tmp;
stree[rt<<].set=stree[rt<<|].set=tmp;
stree[rt<<].sset=stree[rt<<|].sset=true;
/*stree[rt].lazy=0;*/stree[rt<<].lazy=;stree[rt<<|].lazy=;
//return;
}
if(stree[rt].lazy!=)
{
LL tmp=stree[rt].lazy;stree[rt].lazy=;
stree[rt<<].sum+=tmp*(m-(m>>));
stree[rt<<|].sum+=tmp*(m>>);
stree[rt<<].ma+=tmp;stree[rt<<|].ma+=tmp;
stree[rt<<].mi+=tmp;stree[rt<<|].mi+=tmp;
stree[rt<<].lazy+=tmp;stree[rt<<|].lazy+=tmp;
}
}
void build(int l, int r, int rt)
{
if(l==r)
{
LL tmp;scanf("%lld", &tmp);
stree[rt].sum=stree[rt].ma=stree[rt].mi=tmp;
stree[rt].lazy=stree[rt].set=stree[rt].sset=;
return;
}
int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt);
}
void update_set(int L, int R, LL s, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
stree[rt].sum=(LL)s*(r-l+);
stree[rt].ma=stree[rt].mi=s;
stree[rt].set=s;
stree[rt].sset=true;
stree[rt].lazy=;
pushdown(rt, r-l+);
return;
}
pushdown(rt, r-l+);
int m=(l+r)>>;
if(L<=m) update_set(L, R, s, lson);
if(m<R) update_set(L, R, s, rson);
pushup(rt);
}
void update_add(int L, int R, LL c, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
stree[rt].sum+=(LL)c*(r-l+);
stree[rt].ma+=c;
stree[rt].mi+=c;
stree[rt].lazy+=c;
pushdown(rt, r-l+);
return;
}
pushdown(rt, r-l+);
int m=(l+r)>>;
if(L<=m) update_add(L, R, c, lson);
if(m<R) update_add(L, R, c, rson);
pushup(rt);
}
LL query_sum(int L, int R, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
return stree[rt].sum;
}
pushdown(rt, r-l+);
int m=(l+r)>>;
LL res=;
if(L<=m) res+=query_sum(L, R, lson);
if(m<R) res+=query_sum(L, R, rson);
return res;
}
LL query_ma(int L, int R, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
return stree[rt].ma;
}
pushdown(rt, r-l+);
int m=(l+r)>>;
LL res=-loo;
if(L<=m) res=max(res, query_ma(L, R, lson));
if(m<R) res=max(res, query_ma(L, R, rson));
return res;
}
LL query_mi(int L, int R, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
return stree[rt].mi;
}
pushdown(rt, r-l+);
int m=(l+r)>>;
LL res=loo;
if(L<=m) res=min(res, query_mi(L, R, lson));
if(m<R) res=min(res, query_mi(L, R, rson));
return res;
}
int main(int argc, char *argv[])
{
int m, n;
while(scanf("%d%d", &n, &m)==)
{
M(stree, );
build(, n, );
while(m--)
{
char cz[];scanf("%s", cz);
if(cz[]=='d')
{
int l, r;LL c;scanf("%d%d%lld", &l, &r, &c);
update_add(l, r, c, , n, );
}
else if(cz[]=='e')
{
int l, r;LL c;scanf("%d%d%lld", &l, &r, &c);
update_set(l, r, c, , n, );
}
else if(cz[]=='u')
{
int l, r;scanf("%d%d", &l, &r);
printf("%lld\n", query_sum(l, r, , n, ));
}
else if(cz[]=='a')
{
int l, r;scanf("%d%d", &l, &r);
printf("%lld\n", query_ma(l, r, , n, ));
}
else
{
int l, r;scanf("%d%d", &l, &r);
printf("%lld\n", query_mi(l, r, , n, ));
}
}
}
return ;
}