사실 별건 아닌데, 내가 애초에 세그 트리를 비재귀로 구현하다 보니가, 레이지가 너무 안 익숙해서 정리한다. 레이지는 대부분 재귀로 구현하고 (비재귀 방식도 있다고는 한다...) 그렇다 보니까 구현도 길어지고 그러는데, 나중에 scpc같은 곳에서 팀노트 없을 때 빠르게 구현해 낼 자신이 없을 때 가끔 써먹어야 겠다... 아 근데 (금광 + 레이지) 세그 비재귀로 짤때는 잘 써먹고 있다. 시간복잡도는 O(nloglogn)인데, 다음과 같은 방식을 이용한다. 1. 업데이트: 구간 [L,R]에 c만큼 더하기. 세그트리 base이기 때문에 최대 특정 길이의 구간은 logN개의 노드로 분할된다. 현재 노드를 x라 하자. 이 노드에 다음과 같은 작업을 할 것이다. 이 노드의 자식 노드들을 업데이트 하지는 않는다. ..
