Fenwick Tree 펜윅 트리 기존의 펜윅 트리에 대해서는 깔끔하게 설명하신 백준님의 게시글을 보고 오자. 펜윅 트리 (바이너리 인덱스 트리) - BaekJoon 펜윅 트리는 세그먼트 트리와는 다르게 부분 합(첫 원소에서 부터 i개의 값)을 계산하는데 특화되었다.(이 특징이 가장 중요합니다!!!) 백준 님이 설명한 펜윅 트리에서는 점 업데이트(Point Update)와 구간 쿼리(Range query)가 가능하다. 따라서 [L,R]구간의 구간합은 [1,R]까지의 합(pSum(R) ) - [1,L-1]까지의 합( pSum(L-1) )으로 구할 수 있다. 하지만 원소의 업데이트는 한 개씩만 진행할 수 있다. 따라서 백준 - 수열과 쿼리 21(16975) 문제와 같은 구간의 업데이트를 요구하는 문제는 일일..

문제 https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 solved.ac 난이도: Paltium 4 백준- 수열과 쿼리 21(16975)와 동일한 문제. 수열과 쿼리 문제는 펜윅 트리로 풀었지만 위의 문제와 같이 느리게 갱신되는 세그먼트 트리(lazy propagation)로 해결 가능하다. 프로그래밍 분야에서 lazy라는 의미는 계산이 필요할 때까지 최대한 처리를 늦추는 방..