글 읽기 - 구간합구하기2 펜윅트리 c++

akrnote 3년 전 0

펜윅트리로 해보았는데 계속해서 시간초과가 납니다. 배열을 하나 더 선언하여 연산량을 줄였다고 생각했는데도 시간초과가 나네요...조언 부탁드리겠습니다.

```
#include<bits/stdc++.h>
#define ll long long

using namespace std;

int n,m,k;
ll fen[1000001];
ll total[1000001]={0,};

void add(int at, ll val){
	while(at<=n){
		fen[at]+=val;
		at+=at&-at;
	}
}

ll sum(int at){
	if(at==0) return 0;
	ll result=0;
	while(at>0){
		result +=fen[at];
		at-=at&-at;
	}
	return result;
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1; i<=n; i++){
		ll x;
		scanf("%lld",&x);
		add(i,x);
	}
	for(int i=0; i<m+k; i++){
		int x;
		scanf("%d",&x);
		if(x==1){
			int a,b;
			ll val;
			scanf("%d%d%lld",&a,&b,&val);
			for(int j=a; j<=b; j++){
				total[j]+=val;
			}
		}
		else if(x==2){
			int a,b;
			scanf("%d%d",&a,&b);
			for(int j=a; j<=b; j++){
				if(total[j]==0) continue;
				add(j,total[j]);
				total[j]=0;
			}
			printf("%lld\n",sum(b)-sum(a-1));
			
		}
	}
}
```

Green55 3년 전 1

일반적인 펜윅트리로는 풀기 힘듭니다. 레이지를 공부해보세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

구간합구하기2 펜윅트리 c++

akrnote 3년 전 0

Green55 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말