저도 펜윅트리 공부하면서 이 문제 풀어봤습니다
0의 개수를 저장하는 펜윅과, 곱셈 결과를 저장하는 펜윅 (즉, 2개의 트리)로 구성했구요
0을 입력받으면 값을 1로 수정하고 0을 카운팅해서 기록했습니다 (값이 수정될 때 마다, 0의 개수를 업데이트했습니다)
[a, b] 구간의 곱을 출력할때, [0, a)의 0의 개수와 [0, b]의 0의 개수가 다르다면, 결과값은 0을 출력합니다.
저는 오히려 나머지 연산자의 역원에서 어려웠어요.. (이 부분은 extended euclid 이용해서 해결했습니다)
최적화된 코드는 아니지만 시도에 의의를 두었습니다.
dlqudrjs 4년 전
구간합은 세그먼트로 풀었고, 구간곱은 공부겸 펜윅트리로 시도해보고있는데 펜윅트리로 풀 수 있나요?
지금 가장 안되는부분이 갱신할때 차이만큼 계속 업데이트해줘야 하는데, 나눗셈을 나머지 연산자 역원으로 구해준다고 쳐도 중간에 0이 있는경우가 상상이 안가네요.ㅜㅠ