线段树

区间+等差数列 区间求和

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

const int N=2e5+5;
const int mod=998244353;
const int iv=(mod+1)/2;
//维护区间+等差数列 以及 区间和. 

ll a[N];

struct Seg{
	ll sum;
	pair<ll,ll>lz;
}Tr[N<<2];

void pushdown(int u,ll l,ll r)
{
	if(Tr[u].lz.second!=0)
	{
		ll d=Tr[u].lz.second;
		ll c=Tr[u].lz.first;
		int mid=(l+r)>>1;
		Tr[u<<1].sum=(Tr[u<<1].sum+1ll*(c+1ll*(c+1ll*(mid-l)*d%mod))*(mid-l+1)%mod*iv%mod)%mod;
		Tr[u<<1].sum+=mod,Tr[u<<1].sum%=mod;
		Tr[u<<1|1].sum=(Tr[u<<1|1].sum+1ll*((c+1ll*(r-l)*d%mod)%mod+(c+1ll*(mid-l+1)*d%mod))%mod*(r-mid)%mod*iv%mod)%mod;
		Tr[u<<1|1].sum+=mod,Tr[u<<1|1].sum%=mod;
		Tr[u<<1].lz={Tr[u<<1].lz.first+(c)%mod,(Tr[u<<1].lz.second+d)%mod};
		Tr[u<<1|1].lz={Tr[u<<1|1].lz.first+(c+1ll*d*(mid-l+1)%mod)%mod,(Tr[u<<1|1].lz.second+d)%mod};
		Tr[u].lz={0,0};
	}
}

void update(int u,ll l,ll r,ll L,ll R,ll d)
{
	if(L>r||R<l)	return;
	if(L<=l&&r<=R)
	{
		
		Tr[u].sum=(Tr[u].sum+1ll*(1ll*(l-L+1)*d%mod+1ll*(r-L+1)*d%mod)*(r-l+1)%mod*iv%mod)%mod;
		Tr[u].sum+=mod,Tr[u].sum%=mod;
		Tr[u].lz={(Tr[u].lz.first+1ll*(l-L+1)*d)%mod,(Tr[u].lz.second+d)%mod};
		return;
	}
	pushdown(u,l,r);
	ll mid=(l+r)>>1;
	update(u<<1,l,mid,L,R,d);
	update(u<<1|1,mid+1,r,L,R,d);
	Tr[u].sum=(Tr[u<<1].sum+Tr[u<<1|1].sum)%mod;
	Tr[u].sum+=mod,Tr[u].sum%=mod;
}//L,R是要加等差序列的区间.公差为d. 

ll query(int u,int l,int r,int L,int R)
{
	if(L>r||R<l)	return 0;
	if(L<=l&&r<=R)	return (Tr[u].sum%mod);
	int mid=(l+r)>>1;
	pushdown(u,l,r);
	return ((query(u<<1,l,mid,L,R)+query(u<<1|1,mid+1,r,L,R))%mod+mod)%mod;
}

int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		update(1,1,n,i,n,a[i]);
	}
	while(q--)
	{
		int op;
		scanf("%d",&op);
		if(op==1)
		{
			int id;ll x;
			scanf("%d%lld",&id,&x);
			ll cha=x-a[id];
			update(1,1,n,id,n,cha);
			a[id]=x;
		}
		else
		{
			int id;
			scanf("%d",&id);
			printf("%lld\n",(query(1,1,n,1,id)%mod+mod)%mod);
		}
	}
	return 0;
} 
/*

5 5
0 0 0 0 1
1 1 
1 2 2
1 3 3
1 4 4
2 4

35

5 6
0 0 0 0 1
1 1 1
1 2 2
2 1
2 2
2 3
2 4

*/