4 solutions

  • 3
    @ 2024-12-28 10:20:42

    建议配合上一篇题解食用

    为了节省篇幅，本题解只讲与上一题有区别的地方。所以还是建议先看上一篇题解。

    题意

    维护一个区改区查，修改为加操作，查询为区间和。

    思路

    和上一篇最大的区别，在于要区改。

    区改，最简单的方式便是一个一个地单改，单改时间复杂度为O(logn)O(log_n)，那么一个个改时间复杂度为O(nlogn)O(nlog_n)，最后总时间复杂度O(mnlogn)O(mnlog_n)，显然会超时。

    那么有一个形象的比喻：

    你是一个课代表，老师一布置作业你就告诉组长，再让组长告诉组员，这样的时间复杂度很高。

    有一天，你想到了一个新方法（就是本题解法），等老师要抽查某组作业的时候再告诉相应组长让他们赶紧写，时间复杂度就降低了。

    也就是说，修改操作只需要找到要加的组并附上一个待做作业值，那么时间复杂度和上一题的查询相同，O(logn)O(log_n)，然后真改就是与查询同步进行，不消耗时间复杂度等级。

    那么这个待做作业值就是lazy标记（在我的代码里面表示为add数组）。

    从函数层面上看，就比上一题多了个PushDown()（实际修改，时间复杂度O(1)O(1)）。

    PushUp

    最简单的函数，与上一题无异。

    PushDown

    目的

    把节点的add标记推到字数并清空add标记。

    写法

    不就是把目的翻译成C++代码吗？

    void PushDown(int i,int l,int r){
	int mid=l+r>>1,lenl=mid-l+1,lenr=r-mid;
	//lenl和lenr是左右子树长度。 
	tr[i<<1]+=add[i]*lenl;//这里也要乘上长度。 
	tr[i<<1|1]+=add[i]*lenr;
	add[i<<1]+=add[i];//推下去 
	add[i<<1|1]+=add[i];
	add[i]=0;//清空 
}

    Build

    与上一题无异。

    UpDate

    与上一题区别最大。（或者除去多出来的PushDown()？）

    首先，如果修改区间包含当前节点，那么就直接修改本节点值，不再向下递归，同时在add数组上面做记号，意思是当前节点已经加但下面节点未加的值。

    如果不包含，就一次查看左右子树是否有重（chóng），然后递归修改有效子树。

    void UpDate(int i,int l,int r,int x,int y,long long k){
	if(x<=l&&r<=y){//被包含。 
		tr[i]+=(r-l+1)*k;
		//因为下面每一个都要加k，所以要乘上长度。 
		add[i]+=k;
		return;
	}
	PushDown(i,l,r);//把状态更新下去才能递归。 
	int mid=l+r>>1;
	if(x<=mid)//左边界要改 
		UpDate(i<<1,l,mid,x,y,k);
	if(mid<y)//右边界要改 
		UpDate(i<<1|1,mid+1,r,x,y,k);
	PushUp(i); 
}

    Query

    写法

    取决于查询。这里是加和。

    比较不难。（在区改区查线段树里面）（难度其实增加了，但是PushDown()和UpDate()比她增加的难度更多）

    与上题没有太大差异，就是在递归前要先PushDown。

    long long Query(int i,int l,int r,int x,int y){
	if(x<=l&&r<=y)
		return tr[i];
	PushDown(i,l,r);//不更新状态查询子树怎么得到正确结果？ 
	int mid=l+r>>1;
	long long ret=0;
	if(x<=mid)
		ret+=Query(i<<1,l,mid,x,y);
	if(mid<y) 
		ret+=Query(i<<1|1,mid+1,r,x,y);
	return ret;
}

    代码

    /*************************************\
全部使用long long不是好习惯，
我们最好分清楚哪些是int那些是long long。 
\*************************************/
#include<iostream>
#define N int(6e5)
using namespace std;
int n=0;
long long a[N]{},tr[4*N]{},add[4*N];
void PushUp(int i){
	tr[i]=tr[i<<1]+tr[i<<1|1];
}
void PushDown(int i,int l,int r){
	int mid=l+r>>1,lenl=mid-l+1,lenr=r-mid;
	//lenl和lenr是左右子树长度。 
	tr[i<<1]+=add[i]*lenl;
	tr[i<<1|1]+=add[i]*lenr;
	add[i<<1]+=add[i];
	add[i<<1|1]+=add[i];
	add[i]=0;//清空 
}
void Build(int i,int l,int r){
	if(l==r){
		tr[i]=a[l];
		return;
	}  
	int mid=l+r>>1;
	Build(i<<1,l,mid);
	Build(i<<1|1,mid+1,r);
}
void UpDate(int i,int l,int r,int x,int y,long long k){
	if(x<=l&&r<=y){//被包含。 
		tr[i]+=(r-l+1)*k;
		//因为下面每一个都要加k，所以要乘上长度。 
		add[i]+=k;
		return;
	}
	PushDown(i,l,r);//把状态更新下去才能递归。 
	int mid=l+r>>1;
	if(x<=mid)//左边界要改 
		UpDate(i<<1,l,mid,x,y,k);
	if(mid<y)//右边界要改 
		UpDate(i<<1|1,mid+1,r,x,y,k);
	PushUp(i); 
}
long long Query(int i,int l,int r,int x,int y){
	if(x<=l&&r<=y)
		return tr[i];
	PushDown(i,l,r);//不更新状态查询子树怎么得到正确结果？ 
	int mid=l+r>>1;
	long long ret=0;
	if(x<=mid)
		ret+=Query(i<<1,l,mid,x,y);
	if(mid<y) 
		ret+=Query(i<<1|1,mid+1,r,x,y);
	return ret;
}
int main(){ 
	int m=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	Build(1,1,n);
	while(m--){
		int op=0;
		cin>>op;
		if(op==1){
			int x=0,y=0;
			long long k=0;
			cin>>x>>y>>k;
			UpDate(1,1,n,x,y,k);
		}
		if(op==2){
			int x=0,y=0;
			cin>>x>>y;
			cout<<Query(1,1,n,x,y)<<"\n";
		}
	}
	return 0;
}

    tips

    本题目需要使用long long，但是建议不要直接一网打尽#define int long long，而是注意像n，l，r之类的是不用开long long的，只有a，tr，add，ret之类的需要开。

    Query函数需要开long long！别问我怎么知道的！

    • @ 2024-12-31 19:30:37

      深表歉意

      很对不起，在原来的完整代码开头注释中，我将“哪些”误打成“那些”。现已更正，在此再次表示歉意。

    • @ 2025-1-16 16:54:43

      优质题解，必须好评！

  • 2
    @ 2024-12-10 19:03:27

    线段树写法,当然,树状数组也可以做

    题解

    区改区查

    思路

    线段树,模板题,看题解没有用的,还是要去学

    线段树自学网址

    代码

    #include<iostream>
#define N 100005
#define int long long
using namespace std;
int n,m;
int tree[4*N];//四倍空间 
int lazy[4*N];
int a[N];

void btree(int l,int r,int x)//建树 
// l:当前左区间,r:当前右区间,x:当前节点 
{
	if(l==r)//单点的时候 
	{
		tree[x]=a[l];//标记 
		return;
	}
	int m=(l+r)>>1;
	btree(l,m,x*2);//递归左子树 
	btree(m+1,r,x*2+1);//递归右子树 
	tree[x]=tree[x*2]+tree[x*2+1];//左右子树的和 
}
void btree()//懒得写参数 
{
	btree(1,n,1);
}

int gtree(int l,int r,int s,int t,int x)//区查 
// l:要查的左区间,r:要查的右区间,s:当前左区间,t:当前右区间,x:当前节点 
// 必须要看一下是如何传参的,很容易错!!! 
// gtree(l,r,1,n,1) s,t,x是1,n,1 
{
	if(l<=s && t<=r)//有现成的 
		return tree[x];
	int m=(s+t)>>1,sum=0;
	if(lazy[x])//有懒标记,要分配给子节点 
	{
		tree[x*2]+=lazy[x]*(m-s+1);//传给左子树,m-s+1是左区间的长度 
		tree[x*2+1]+=lazy[x]*(t-m);//传给右子树, t-m 是右区间的长度 
		lazy[x*2]+=lazy[x];  //懒标记传给左子树 
		lazy[x*2+1]+=lazy[x];//懒标记传给右子树 
		lazy[x]=0;//懒标记传完了,清空 
	}
	if(l<=m)
		sum+=gtree(l,r,s,m,x*2);//递归左子树 
	if(r>m)
		sum+=gtree(l,r,m+1,t,x*2+1);//递归右子树 
	return sum;
}
int gtree(int l,int r)//懒得写参数 
{
	return gtree(l,r,1,n,1);//注意是如何传参数的 
}
void utree(int l,int r,int s,int t,int c,int x)//区改
// l:要查的左区间,r:要查的右区间,s:当前左区间,t:当前右区间,c:更改的值,x:当前节点 
// 必须要看一下是如何传参的,很容易错!!! 
// utree(l,r,1,n,c,1) s,t,x是1,n,1 
{
	if(l<=s && t<=r)//有现成的 
	{
		tree[x]+=(t-s+1)*c;//更新区间和 
		lazy[x]+=c;//记得要懒标记 
		return;
	}
	int m=(s+t)>>1;
	if(lazy[x] && s!=t)//有懒标记,而且不是单点 
	{
		//一样的东西 
		tree[x*2]+=lazy[x]*(m-s+1);
		tree[x*2+1]+=lazy[x]*(t-m);
		lazy[x*2]+=lazy[x];
		lazy[x*2+1]+=lazy[x];
		lazy[x]=0;
	}
	if(l<=m)
		utree(l,r,s,m,c,x*2);//递归左子树 
	if(r>m)
		utree(l,r,m+1,t,c,x*2+1);//递归右子树 
	tree[x]=tree[x*2]+tree[x*2+1];//更新区间和 
}
void utree(int l,int r,int c)//懒得写参数 
{
	utree(l,r,1,n,c,1);//注意是如何传参数的 
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	btree();
	while(m--)
	{
		int o,l,r,k;
		cin>>o;
		if(o==1)//区改 
		{
			cin>>l>>r>>k;
			utree(l,r,k);
		}
		if(o==2)//区查 
		{
			cin>>l>>r;
			cout<<gtree(l,r)<<"\n";
		}
	}
	return 0;
}
    • 1
      @ 2024-12-5 13:54:25 
      #include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[100005];
int b[100005];
int c1[100005];
int c2[100005];
int lowbit(int x){
	return x&(-x);
}
int sum1(int x){
	int ret=0;
	for(int i=x;i>0;i-=lowbit(i)){
		ret+=c1[i];
	}
	return ret;
}
void add1(int x,int y){
	for(int i=x;i<=n;i+=lowbit(i)){
		c1[i]+=y;
	}
}
int sum2(int x){
	int ret=0;
	for(int i=x;i>0;i-=lowbit(i)){
		ret+=c2[i];
	}
	return ret;
}
void add2(int x,int y){
	for(int i=x;i<=n;i+=lowbit(i)){
		c2[i]+=y;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i]-a[i-1];
		add1(i,b[i]);
		add2(i,i*b[i]);
	}
	for(int i=1;i<=m;i++){
		int f;
		cin>>f;
		if(f==1){
			int x,y,k;
			cin>>x>>y>>k;
			add1(x,k);
			add1(y+1,-k);
			add2(x,k*x);
			add2(y+1,-k*(y+1));
		}
		else{
			int x,y;
			cin>>x>>y;
			cout<<((y+1)*sum1(y)-sum2(y))-((x)*sum1(x-1)-sum2(x-1))<<"\n";
		}
	}
}
      • 1
        @ 2024-12-5 13:39:21

        题意

        这道题是模板 1 和模板 2 的结合体。

        思路

        结合模板 2 的思路，手推一下，不难得出：我们需要两个树状数组，一个存原数组，一个存修改数据的差分。输出时输出 cr−cl−1+∑i=lrbic_r-c_{l-1}+\displaystyle\sum_{i=l}^rb_i，其中 cc 是原数组的树状数组，bb 是修改数据的树状数组。

        代码

        我的代码用了我自己写的树状数组模板[1]，大家看懂思路其实就可以做出来了。

        #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename tp>
class BIT{
	private:
		size_t n;
		vector<tp> c;
		size_t lowbit(size_t x){
			return x & -x;
		}
	public:
		BIT(size_t n){
			this->n = n;
			c = vector<tp>(n);
		}
		BIT(vector<tp> a){
			n = a.size();
			c = vector<tp>(n);
			for (size_t i = 1;i <= n;i++){
				add(i,a[i]);
			}
		}
		BIT(tp *a,size_t n){
			this->n = n;
			c = vector<tp>(n);
			for (size_t i = 1;i <= n;i++){
				add(i,a[i]);
			}
		}
		BIT(BIT<tp> &a){
			n = a.size();
			c = a;
		}
		size_t size(){
			return n;
		}
		void add(size_t i,tp val){
			for (;i <= n;i += lowbit(i))
				c[i] += val;
		}
		tp query(size_t r){
			tp res = 0;
			for (;r;r -= lowbit(r))
				res += c[r];
			return res;
		}
		tp query(size_t l,size_t r){
			return query(r) - query(l - 1);
		}
};
const int N = 1e5 + 5;
int n,m,a[N];
BIT<ll> c(N),b(N);
int main(int argc, char **argv){
	cin >> n >> m;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		c.add(i,a[i]);
	}
	while (m--){
		int op;
		cin >> op;
		if (op == 1){
			int l,r;
			ll x;
			cin >> l >> r >> x;
			b.add(l,x),b.add(r + 1,-x);
		}else{
			int l,r;
			cin >> l >> r;
			ll sum = c.query(l,r);
			for (int i = l;i <= r;i++){
				sum += b.query(i);
			}
			printf("%lld\n",sum);
		}
	}
	return 0;
}

        1. 点我查看 ↩︎

        • 1

        【模板】线段树 1

        Information

        ID
        283
        Time
        1000ms
        Memory
        125MiB
        Difficulty
        9
        Tags
        # Submissions
        110
        Accepted
        10
        Uploaded By
        1. About
        2. Contact Us
        3. Privacy
        4. Terms of Service
        5. Copyright Complaint
        6. Language
        7. Legacy mode
        8. Theme
        2. 粤ICP备2022044963号-1
        3. Worker 0, 31ms
        4. Powered by Hydro v4.13.3 Community