P3372 洛谷线段树1模板的多种解法

2023-12-02 18:58:16

线段树1的多种解法

B y By By q w q qwq qwq_ v o l c a n o ( D a r k volcano(Dark volcano(Dark _ v o l c a n o ) volcano) volcano)
l u o g u luogu luogu:qwq_volcano
Link:P3372

此篇文章着重于介绍树状数组解法

Tips:记得开 l o n g l o n g long long longlong

Update:2022/1/31 年三十

线段树

普通线段树:
不用多说，直接上code

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
struct node{
	int tag;
	int data;
	int l;
	int r;
}tree[400001];
int n,m,a[100001],ans;
int yezi(int k){//判断叶子节点
	return (tree[k].l==tree[k].r);
}
void build(int l,int r,int k){//建树
	tree[k].l=l;tree[k].r=r;
	if(yezi(k)){
		tree[k].data=a[tree[k].l];
		return ;
	}
	int mid=(tree[k].l+tree[k].r)>>1;
	build(tree[k].l,mid,k*2);
	build(mid+1,tree[k].r,k*2+1);
	tree[k].data=tree[k*2].data+tree[k*2+1].data;
}
void push_down(int k){//懒标记下传
	tree[k*2+1].tag+=tree[k].tag;
	tree[k*2].tag+=tree[k].tag;
	tree[k*2+1].data+=tree[k].tag*(tree[k*2+1].r-tree[k*2+1].l+1);
	tree[k*2].data+=tree[k].tag*(tree[k*2].r-tree[k*2].l+1);
	tree[k].tag=0;
}
void Sum(int x,int y,int k){//区间求和 [x~y]
	if(x<=tree[k].l&&y>=tree[k].r){
		ans+=tree[k].data;
		return ;
	}
	if(tree[k].tag) push_down(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(x<=mid) Sum(x,y,k*2);
	if(y>mid) Sum(x,y,k*2+1);
}
int Ask(int k,int q){//单点查询 本文并没有用到 可以用区间查询代替
	if(yezi(k)) return tree[k].data;
	int mid=(tree[k].l+tree[k].r)>>1;
    if(tree[k].tag) push_down(k);
	if(q<=mid) Ask(2*k,q);
	else Ask(2*k+1,q); 
}
void Add(int k,int q){//单点加 同样没有用
	if(tree[k].l==tree[k].r){
		tree[k].data+=q;
		tree[k].tag+=q;
		return ;
	}
	if(tree[k].tag) push_down(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(q<=mid) Add(k*2,q);
	else Add(k*2+1,q);
	tree[k].data=tree[k*2].data+tree[k*2+1].data;
}
void Change(int k,int x,int y,int q){//区间加
	if(x<=tree[k].l&&y>=tree[k].r){
		tree[k].data+=(tree[k].r-tree[k].l+1)*q;
		tree[k].tag+=q;
		return ;
	}
	if(tree[k].tag) push_down(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(x<=mid) Change(k*2,x,y,q);
	if(y>mid) Change(k*2+1,x,y,q);
	tree[k].data=tree[k*2].data+tree[k*2+1].data;
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	    scanf("%d",a+i);
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int w,x,y,k;
		scanf("%lld%lld%lld",&w,&x,&y);
		if(w==1){
			scanf("%lld",&k);
			Change(1,x,y,k);
		}
		else{
			ans=0;
			Sum(x,y,1);
			printf("%lld\n",ans);
		}
	}
}

指针线段树 (慢300-400ms,~~吸氧后差不多~~)

//ask_interval_sum 区间求和 add_interval区间加
#include<iostream>
using namespace std;
template <typename ITEM>
class seg_tree{
	private:
	struct node{
		ITEM data;
		ITEM Lazytag_add;
		int l,r;
		node *lc,*rc;
	}*root;
	void push_down(node **Rot){
		(*Rot)->lc->Lazytag_add+=(*Rot)->Lazytag_add;
		(*Rot)->rc->Lazytag_add+=(*Rot)->Lazytag_add;
		(*Rot)->lc->data+=((*Rot)->lc->r-(*Rot)->lc->l+1)*((*Rot)->Lazytag_add);
		(*Rot)->rc->data+=((*Rot)->rc->r-(*Rot)->rc->l+1)*((*Rot)->Lazytag_add);
		(*Rot)->Lazytag_add=0;
	}
	node *hbuild(ITEM a[],node ** Rot,int l,int r){
		*Rot=new node;
		(*Rot)->l=l;
		(*Rot)->r=r;
		if(l==r){
			(*Rot)->data=a[l];
			(*Rot)->lc=NULL;
			(*Rot)->rc=NULL;
			return (*Rot);
		}
		int mid=(l+r)>>1;
		(*Rot)->lc=hbuild(a,&((*Rot)->lc),l,mid);
		(*Rot)->rc=hbuild(a,&((*Rot)->rc),mid+1,r);
		(*Rot)->data=(*Rot)->lc->data+(*Rot)->rc->data;
		return (*Rot);
	}

	ITEM Ask_I_S(node **Rot,int ql,int qr){
		ITEM res=0;
		if((*Rot)->l>=ql&&(*Rot)->r<=qr){
			res+=(*Rot)->data;
			return res;
		}
		if((*Rot)->Lazytag_add) push_down(&(*Rot));
		int mid=((*Rot)->l+(*Rot)->r)>>1;
		if(ql<=mid) res+=Ask_I_S(&((*Rot)->lc),ql,qr);
		if(qr>mid) res+=Ask_I_S(&(*Rot)->rc,ql,qr);
		return res;
	}
	void ADD_I_S(node **Rot,int ql,int qr,int k){
		if((*Rot)->l>=ql&&(*Rot)->r<=qr){
			(*Rot)->data+=((*Rot)->r-(*Rot)->l+1)*k;
			(*Rot)->Lazytag_add+=k;
			return ;
		}
		if((*Rot)->Lazytag_add){push_down(&(*Rot));}
		int mid=((*Rot)->l+(*Rot)->r)>>1;
		if(ql<=mid) ADD_I_S(&((*Rot)->lc),ql,qr,k);
		if(qr>mid) ADD_I_S(&(*Rot)->rc,ql,qr,k);
		(*Rot)->data=(*Rot)->lc->data+(*Rot)->rc->data;
	}
	public:
	void build(ITEM a[],int l,int r){
		hbuild(a,&root,l,r);
	}
	void Show(node *ROt){
		cout<<ROt->data<<" ";
		if(ROt->lc) Show(ROt->lc);
		if(ROt->rc) Show(ROt->rc);
	}
	void DebugShow(){
		Show(root);
	}
	ITEM ask_interval_sum(int l,int r){
		return Ask_I_S(&root,l,r);
	}
	void add_interval(int l,int r,int k){
        ADD_I_S(&root,l,r,k);
	}
};
seg_tree<long long> T;
long long a[100001];
int n,q;
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	T.build(a,1,n);
	while(q--){
        int tag;
        cin>>tag;
        if(tag==1){
            int a,b,c;
            cin>>a>>b>>c;
            T.add_interval(a,b,c);
        }
        if(tag==2){
            int a,b;
            cin>>a>>b;
            cout<<T.ask_interval_sum(a,b)<<endl;
        }
	}
}

分块

浅显易懂，但是有亿点慢(能过)
约2s,吸氧快1s
自己研究出的很独特的写法

//极简分块 ,写法有一点不同
#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
int n;
int T,L;//块数，块长
int a[100001];
int sum[100001],addit[100001];//sum[p]表示第p个块的和,addit[p]表示第p个块的加法标记
int BEGIN(int p){return L*(p-1)+1;}//求第p个块的前端
int END(int p){return min(L*p,n);}//求第p个块的后端
int NUM(int p){return ceil(double(p)/L);} //求包含数a[i]的块的编号
int LENGTH(int p){//求第i个块长
	if(END(p)==n) return n-(T-1)*L;
	else return L;
}
void Prework(){//预处理，大概是最简的吧
	T=ceil(sqrt(double(n))),L=ceil(double(n)/T);
	for(int i=1;i<=n;i++) sum[NUM(i)]+=a[i];
}
//分块的核心,大段维护,小段暴力
void add(int l,int r,int c){
	for(int i=l;i<=END(NUM(l))&&i<=r;++i) a[i]+=c,sum[NUM(i)]+=c;//不是整块的直接暴力加
	if(NUM(l)!=NUM(r)) for(int i=r;i>=BEGIN(NUM(r))&&i>=l;--i) a[i]+=c,sum[NUM(i)]+=c;//同上
	for(int i=NUM(l)+1;i<NUM(r);i++) sum[i]+=(c*LENGTH(i)),addit[i]+=c;//大块维护
}
//查询整体思路和加一样
int ask(int l,int r){
	int ans=0;
	for(int i=l;i<=END(NUM(l))&&i<=r;++i) ans+=(a[i]+addit[NUM(i)]);
	if(NUM(l)!=NUM(r)) for(int i=r;i>=BEGIN(NUM(r))&&i>=l;--i) ans+=(a[i]+addit[NUM(i)]);
	for(int i=NUM(l)+1;i<NUM(r);i++) ans+=sum[i];
	return ans;
}
int Q;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>Q;
	for(int i=1;i<=n;i++) cin>>a[i];
	Prework();
	while(Q--){
		int opt,x,y;
		cin>>opt>>x>>y;
		if(opt==1){int k;cin>>k;add(x,y,k);}
		else {cout<<ask(x,y)<<'\n';}
	}
}

树状数组

给出树状数组函数

int lowbit(int x){//求2^(末尾0的个数) 这里用^代表幂,不是异或
	return x&(-x);
}
void add(int x,int k){//单点加
	for(;x<=n;x+=lowbit(x)) c[x]+=k;
}
int ask(int x){//求前缀和
	int ans=0;
	for(;x>0;x-=lowbit(x)) ans+=c[x];
	return ans;
}

前置知识: 差分,树状数组 “单点更新，区间查询”、“区间更新，单点查询”

“区间更新，区间查询”：
由"区间更新,单点查询"的前置知识，可以得出此题区间更新仍需要维护差分数组
设数列长度为 n n n,原数组为 a [ 1 a[1 a[1~ n ] n] n]
操作区间为 l l l~ r r r
则差分数组 d [ i ] = a [ i ] − a [ i − 1 ] ; d[i]=a[i]-a[i-1]; d[i]=a[i]−a[i−1];

区间更新?

相当于用树状数组维护差分数组
用树状数组维护差分数组,初始化时遍历1~n 不停 a d d ( i , a [ i ] − a [ i − 1 ] ) ; add(i,a[i]-a[i-1]); add(i,a[i]−a[i−1]);
更新只需要修改两次，假设加上w ,即 a d d ( l , w ) add(l,w) add(l,w) a d d ( r + 1 , − w ) add(r+1,-w) add(r+1,−w)

单点查询?

就是求差分数组的前缀和,如果查询第i个数就是查询代表差分数组的树状数组,即 ask(i)

区间查询?

设查询原数组的前缀和为 A s k ( x ) Ask(x) Ask(x)
那么 A s k ( x ) = ∑ i = x r a s k ( i ) Ask(x)=\sum_{i=x}^r ask(i) Ask(x)=∑i=xrask(i)
让我们展开它
　　　　　　　　　 A s k ( x ) = a s k ( 1 ) + a s k ( 2 ) + . . . + a s k ( x ) Ask(x)=ask(1)+ask(2)+...+ask(x) Ask(x)=ask(1)+ask(2)+...+ask(x)
因为 a s k ask ask 又是求前缀和即 a s k ( i ) = ∑ j = 1 i d [ j ] ask(i)=\sum_{j=1}^i d[j] ask(i)=∑j=1id[j]
所以
　　　　　　　　 A s k ( x ) = ∑ j = 1 1 d [ j ] + ∑ j = 1 2 d [ j ] + . . . + ∑ j = 1 x d [ j ] Ask(x)=\sum_{j=1}^1 d[j]+\sum_{j=1}^2 d[j]+...+\sum_{j=1}^x d[j] Ask(x)=∑j=11d[j]+∑j=12d[j]+...+∑j=1xd[j]
即
　　　　　　　　 A s k ( x ) = x × d [ 1 ] + ( x − 1 ) × d [ 2 ] + . . . + 1 × d [ x ] Ask(x)=x\times d[1]+(x-1)\times d[2]+...+1\times d[x] Ask(x)=x×d[1]+(x−1)×d[2]+...+1×d[x]
又可以变成
　　　　　　　　　　　 A s k ( x ) = ∑ i = 1 x d [ i ] × ( x − i + 1 ) Ask(x)=\sum_{i=1}^x d[i]\times (x-i+1) Ask(x)=∑i=1xd[i]×(x−i+1)
利用乘法分配律,又可以变成
　　　　　　　　　 A s k ( x ) = ( x + 1 ) × ∑ i = 1 x d [ i ] − ∑ i = 1 x d [ i ] × i Ask(x)=(x+1)\times \sum_{i=1}^x d[i] - \sum_{i=1}^xd[i]\times i Ask(x)=(x+1)×∑i=1xd[i]−∑i=1xd[i]×i
即
　　　　　　　　　　 A s k ( x ) = ( x + 1 ) × a s k ( x ) − ∑ i = 1 x d [ i ] × i Ask(x)=(x+1)\times ask(x) - \sum_{i=1}^xd[i]\times i Ask(x)=(x+1)×ask(x)−∑i=1xd[i]×i

这时不能再展开了，只需要再开一个树状数组（或在原树状数组求和与修改的过程中计算）维护 ∑ i = 1 x d [ i ] × i \sum_{i=1}^xd[i]\times i ∑i=1xd[i]×i 即可（两种方案都可以）
记得差分最终答案是 A s k ( r ) − A s k ( l − 1 ) Ask(r)-Ask(l-1) Ask(r)−Ask(l−1)
给出很短的Code:

#include<iostream>
#define int long long
using namespace std;
int c[5000001][2],a[5000001];
int n,m;
int lowbit(int x) {
	return x&(-x);
}
void add(int x,int k,int y){
	for(;x<=n;x+=lowbit(x)) c[x][y]+=k;
}
int ask(int x,int y){
	int ans=0;
	for(;x>0;x-=lowbit(x)) ans+=c[x][y];
	return ans;
}
int ask1(int k){
	return (k+1)*ask(k,0)-ask(k,1);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		add(i,a[i]-a[i-1],0);
		add(i,(a[i]-a[i-1])*i,1);
	}
	for(int i=1;i<=m;i++){
		int opt,x,y,z;
		cin>>opt>>x>>y;
		if(opt==1){
			cin>>z;
			add(x,z,0);
			add(y+1,-z,0);
			add(x,x*z,1);
			add(y+1,-(y+1)*z,1);
		}
		if(opt==2){
			cout<<ask1(y)-ask1(x-1)<<'\n';
		}
	}
}

完结撒花 QwQ
v(｡･ω･｡)
如有问题，私信洛谷或CSDN
本文代码均包含在资源（审核通过后附）

码农公寓