백준 10999- 구간합 구하기 2:
일반 세그먼트 트리는 O(log(N))에서 특정 간격, 최소, 최대, xor, …의 세그먼트 합계를 쿼리할 수 있습니다. 또한 업데이트는 O(log(N)) 시간에도 가능하지만 간격의 길이가 M일 때 주어진 범위에 대한 업데이트는 O(M log(N)) 그다지 매력적인 시간 복잡도가 아닙니다. 게으른 전파는 간격 업데이트를 더 빠르게 하기 위해 나온 아이디어입니다. 적시에 모든 값을 업데이트하는 대신 실제로 업데이트가 필요할 때만 업데이트됩니다. … Read more