글 읽기 - 혹시 제 코드에 문제가 있나요 ㅠㅠ

petil777 9년 전 0

구간합 구하기 문제를 펜윅트리를 이용해서 짜본건데 어디서 틀린지 모르겠습니다...도와주세요 ㅠㅠ

long long int가 발생할만한 곳은 다 해줬다고 생각합니다...

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
struct FenwickTree{
	vector<long long int> tree;
	FenwickTree(int n) : tree(n + 1){}
	long long int sum(int pos){
		long long int ret = 0;
		while (pos>0){
			ret += tree[pos];
			pos &= (pos - 1);
			//pos-=(pos&-pos);
		}
		return ret;
	}
	void add(int pos, long long int val){
		while (pos<tree.size()){
			tree[pos] += val;
			pos += (pos & -pos);
		}
	}
};

int n, m, k;

int main(){

	cin >> n >> m >> k;
	FenwickTree F(n);
	long long int p, c;
	int a, b;
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &p);
		F.add(i, p);
	}
	for (int i = 0; i < m + k; i++)
	{
		scanf("%d %d %lld", &a, &b, &c);
		if (a == 1)
		{
			F.add(b, c - F.tree[b]);
		}
		else
		{
			printf("%lld\n", F.sum(c) - F.sum(b - 1));
		}
	}
}

august14 8년 전 1

add를 F.add(b, c - F.tree[b]);로 처리하셨는데

F에는 원래 값이 저장되는게 아닙니다.

petil777 8년 전 0

개념을 익히다 혼동이 왔네요 ㅠㅠ 해결했습니다! 감사합니다!

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

문제

문제

출처

ICPC

혹시 제 코드에 문제가 있나요 ㅠㅠ

petil777 9년 전 0

august14 8년 전 1

petil777 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말