codeforces.com/contest/1439/problem/C Problem - C - Codeforces codeforces.com 구간 합을 구하고 변경해야 하므로 segment tree로 푸는 문제로 보인다. ecnerwala solution (codeforces.com/contest/1439/submission/98717653) 을 참고했다. segment tree가 뭐지? 배열 구간 (a,b)의 합을 lonN 시간에 구하고 logN의 시간에 수정 할 때 이용되는 이진 트리 구조이다. 시간 복잡도 : O(N) 공간 복잡도 : O(N*2) 최상 위 노드는 (1,N) 합 값을 갖는다. 부모 노드의 구간이 (a, b) 일 때, mid = (a+b)/2라 하면 왼쪽 자식과 오른쪽 자식은 각각 (a,..