求解求解!
  • 板块灌水区
  • 楼主laijingyun
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/5 15:42
  • 上次更新2024/8/5 16:33:59
查看原帖
求解求解!
1176947
laijingyun楼主2024/8/5 15:42

请求大佬解释一下线段树的代码

#include<bits/stdc++.h>
using namespace std;

#define MAXN 100000+50
#define il inline
#define ls(x) (x<<1) 
#define rs(x) (x<<1)+1 

typedef long long ll;

struct Tree
{
	int l,r;
	ll val;
	ll lazy;
};

int n;
ll a[MAXN];

struct SEG
{
	Tree t[MAXN<<2];
	
	il void pushup(int x)
	{
		t[x].val = t[ls(x)].val + t[rs(x)].val;
		return;
	}
	il void pushdown(int x)
	{
		if(t[x].lazy == 0) return;
		t[ls(x)].val += (t[ls(x)].r - t[ls(x)].l + 1) * t[x].lazy;
		t[rs(x)].val += (t[rs(x)].r - t[rs(x)].l + 1) * t[x].lazy;
		t[ls(x)].lazy += t[x].lazy;
		t[rs(x)].lazy += t[x].lazy;
		t[x].lazy = 0;
		return;
	}
	void build(int l, int r, int x)
	{
		t[x].l = l, t[x].r = r;
		if(l == r)
		{
			t[x].val = a[l];
			return;
		}
		int mid = (l + r)>>1;
		build(l, mid, ls(x)),build(mid+1, r, rs(x));
		pushup(x);
		return;
	}
	ll ask(int l, int r, int x)
	{
		if (t[x].r < l || t[x].l > r) 
			return 0;
		if (t[x].r <= r && t[x].l >= l)
		    return t[x].val;
		pushdown(x); 
		return ask(l, r, ls(x))+ask(l, r, rs(x));
	} 
	void add(int l, int r, ll k, int x)
	{
		if (t[x].r < l || t[x].l > r) 
			return;
		if (t[x].r <= r && t[x].l >= l){
		    t[x].val += (t[x].r - t[x].l + 1) *	k;
		    t[x].lazy += k;
		    return;
		}
		pushdown(x);
		add(l, r, k, ls(x)),add(l, r, k, rs(x));
		pushup(x);
		return;
	}
}seg;

int main()
{
	int m, tmp, x, y;
	scanf("%d %d",&n,&m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld",&a[i]);
	}
	seg.build(1, n, 1);
	ll k;
	for (int i = 1; i <= m; i++)
	{
		cin>>tmp;
		switch(tmp)
		{
			case 1:
				cin>>x>>y>>k;
				seg.add(x, y, k, 1);
				break;
			case 2:
				cin>>x>>y;
				cout<<seg.ask(x, y, 1)<<endl;
				break;
		}
	}
	return 0;
}









2024/8/5 15:42
加载中...