非差分树状数组求调
查看原帖
非差分树状数组求调
183026
Cocoly1990楼主2021/7/18 07:24
#include<bits/stdc++.h>
#define ll long long
using namespace std ;
ll tree[2000007] , tree2[2000007] , n , m , a[100007] , x , y , k , ch ;
ll lowbit(ll x)
{
	return x & (- x) ;
}
void add(ll x , ll y)
{
	while(x <= n)
	{
		tree[x] += y ;
		x += lowbit(x) ;
	}
}
ll sum(ll x)
{
	ll ans = 0 ;
	while(x)
	{
		ans += tree[x] ;
		x -= lowbit(x) ;
	}
	return ans ;
}
void add2(ll x , ll y)
{
	while(x <= n)
	{
		tree2[x] += y ;
		x += lowbit(x) ;
	}
}
ll sum2(ll x)
{
	ll ans = 0 ;
	while(x)
	{
		ans += tree2[x] ;
		x -= lowbit(x) ;
	}
	return ans ;
}
int main()
{
	cin >> n >> m ;
	for(ll i = 1 ; i <= n ; i ++)
	{
		cin >> x ;
		a[i] = a[i - 1] + x ;
	}
	for(ll i = 1 ; i <= m ; i ++)
	{
		cin >> ch ;
		if(ch == 1)
		{
			cin >> x >> y >> k ;
			add(x , k) ;
			add2(y , k) ;
		}
		else
		{
			cin >> x >> y ;
			cout << sum(y) << " " << sum2(x - 1) << " " << a[y] - a[x - 1] << endl ;
			cout << sum(y) - sum2(x - 1) + a[y] - a[x - 1] << endl ;
		}
	}
	return 0 ;
}
2021/7/18 07:24
加载中...