差分加树状数组只对一个点求助
查看原帖
差分加树状数组只对一个点求助
206423
焚魂楼主2024/9/11 12:44
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

long long n,m;
long long a[100010],d1[100010],d2[100010],d3[100010];

long long lowbit(long long x) {
	return x&(-x);
}

void add1(long long lo,long long num) {
	for(;lo <= n;lo += lowbit(lo)) {
		d1[lo] += num;
	}
}

void add2(long long lo,long long num) {
	long long tlo = lo;
	for(;lo <= n;lo += lowbit(lo)) {
		d2[lo] += num;
		d3[lo] += tlo*num;
	}
}

long long sum(long long lo) {
	long long tlo = lo,res = 0;
	for(;lo;lo -= lowbit(lo)) {
		res += d1[lo] + (tlo+1) * d2[lo] - d3[lo];
	}
	return res;
}

int main() {
	cin >> n >> m;
	for(long long i = 1;i <= n;i++) {
		cin >> a[i];
		add1(i,a[i]-a[i-1]);
	}
	
	for(long long i = 1;i <= m;i++) {
		long long t,l,r,k,d;
		cin >> t;
		if(t == 1) {
			cin >> l >> r >> k >> d;
			add1(l,k);
			add1(r+1,-k);
			add2(l+1,d);
			add2(r+1,-d);
		}
		else {
			cin >> l;
			cout << sum(l) << endl;
		}
	}
	
	return 0;
}
2024/9/11 12:44
加载中...