[낙 곡] 선분 수 트 리 모양 배열 구간 수정 구간 조회

920 단어 데이터 구조ac 의 길낙 곡
전체 2 점 짜 리 문 제 를 풀 때 이 구간 수정 구간 조회 트 리 배열 을 만 나 손 맛 이 좋 은 것 같 아 가 져 왔 다.증명 하면 그 건 중요 하지 않 아 요. 쓸 줄 알 았 으 면 좋 겠 어 요.
#include
#include
#include
#define maxn 500000
#define LL unsigned long long
using namespace std;
int n,m;
LL a[maxn],sum[maxn],c1[maxn],c2[maxn];
void update(int x,LL y){
	for(int i=x;i<=n;i+=i&(-i))
		c1[i]+=y,c2[i]+=(LL)x*y;
}
LL query(int x){
	LL ans=0;
	for(int i=x;i>0;i-=i&(-i)){
		ans+=(x+1)*c1[i]-c2[i];
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%llu",a+i),sum[i]=sum[i-1]+a[i];
	int pos,a,b;LL c;
	while(m--){
		scanf("%d%d%d",&pos,&a,&b);
		if(pos==1){
			scanf("%llu",&c);
			update(a,c),update(b+1,-c);
		}else{
			printf("%llu
",query(b)-query(a-1)+sum[b]-sum[a-1]);
		}
	}
	return 0;
}
[CSS] 미디어쿼리 적용하기
SelectSort

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage