인프런 커뮤니티 질문&답변
작성한 질문수
8-D 풀이 코드 질문 입니다.
해결된 질문
작성
·
342
·
수정됨
0
강사님 안녕하세요~
풀이해주신 코드에 대해 제가 이해한 것이 맞는지 해서 질문드립니다.
풀이코드
https://www.acmicpc.net/source/share/e2de316babff4d9b808e18926d718fc9
에서 52,54 line 에서 find_index 함수로 부터 구해진 index 에 +1 을 더해주는 이유가,
find_index 함수의 반환값이 0 인 경우 fenwick tree update/sum 의 idx 로 바로 사용할 수 없으므로, find_index 반환 값에 +1 을 한 것으로 이해하면 될까요?
위에서 제가 이해한 내용이 맞다면
아래 제가 제출한 코드와 같이
https://www.acmicpc.net/source/share/5b723f25c81b4f8581fa7fd6caf8f480
sum, update 함수 내부에서 idx 를 1만큼 증가시키는 것도 동일한 것이겠죠?
답변 1
0
안녕하세요 ㅎㅎ
에서 52,54 line 에서 find_index 함수로 부터 구해진 index 에 +1 을 더해주는 이유가,
find_index 함수의 반환값이 0 인 경우 fenwick tree update/sum 의 idx 로 바로 사용할 수 없으므로, find_index 반환 값에 +1 을 한 것으로 이해하면 될까요?
>> 네 맞습니다.
void update(int idx, int value)
{
idx++; // idx = 0 인 경우를 고려하여 +1 을 하여 idx 값의 lower_bound 를 1로 설정하기 위함>> 네 괜찮습니다. 다만 해당 idx++부분은 밖으로 빼시는게 더 좋긴 합니다. update나 sum이라는 함수는 해당 트리의 idx를 중심으로 업데이트, 합을 구한다는 의미를 지니기 때문에 해당 전처리 부분은 밖으로 빼는게 의미상 조금 더 좋은 코드이긴 합니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.