1. 세그먼트 트리 동작 과정
세그먼트 트리는 루트 노드에서 리프 노드까지 범위를 나누어 가며 통일된 연산값을 유지해야 합니다.
따라서 자식 노드에서 부모 노드로 올라가더라도 더 넓어진 범위에 대해 연산 결과를 유지할 수 있어야합니다.
이게 가능한 연산은 최대, 최소, 덧셈, 곱셈 등 일부의 결과로 전체 범위에 적용이 가능한 연산을 세그먼트 트리에 적용할 수 있습니다.
8 크기의 배열에서 3, 2, 5, 3, 5, 2, 3, 4의 값을 가지고 있고, 구간합을 관리하는 세그먼트 트리는 다음과 같습니다.
이 세그먼트 트리에서 2 ~ 8 범위의 구간합을 구하고 싶다면 다음과 같이 구합니다.
찾고자 하는 범위 안에 포함될 때까지 자식으로 내려가며 합을 구하면, 2+8+14로 24라는 것을 알 수 있습니다.
다음으로 세그먼트 트리의 갱신에 대해 살펴 봅시다.
2 ~ 6 범위에 각각 2씩 더한다고 생각해봅시다.
먼저 범위에 해당하는 리프 노드까지 내려간 후 값을 갱신합니다.
그 다음 루트 노드까지 올라오며 값을 갱신합니다.
이렇게 보면 세그먼트 트리는 결국 범위의 크기에 해당하는 모든 리프 노드에 가서 값을 갱신해며 루트 노드까지 올라오므로 비효율적이어 보입니다.
확실히 세그먼트 트리는 갱신(update)보다 구간의 값을 구하는(query) 동작이 효율적입니다.
2. 느리게 갱신되는 세그먼트 트리
만약 update보다 query가 훨씬 많다면 update의 비효율성을 감수하더라도 query의 효율성으로 인해 일반적인 세그먼트 트리를 사용할 수도 있을 것입니다.
하지만 update가 많다면 update의 비효율성을 최소화할 수 있는 최적화가 필요합니다.
query와 update에서 차이가 나는 점은 query는 범위 안에 해당하면 더이상 자식 노드로 내려가지 않으나, update는 리프 노드까지 갱신시켜야하므로 범위 안에 해당하더라도 계속해서 리프 노드를 향해 내려갑니다.
이 부분에서 비효율성이 나타나므로 그 부분에서 최적화하여 효율적으로 동작하도록 합니다.
위에서처럼 2 ~ 6 범위에 2를 더하는 연산을 해봅시다.
굳이 리프 노드까지 내려가지 않고, 쪼개면서 내려가다가 노드가 커버하는 범위가 수정하려는 범위에 포함될 때 더 이상 내려가지 않고 멈춥니다.
그리고 그 자식 노드에 해당하는 lazy 정보를 가지는 tree에 그 값을 기록해둡니다.
이제는 lazy tree에 값이 저장되어있는 곳까지 내려올 일이 없다면(읽기든 갱신이든) 굳이 비효율적으로 갱신하지 않습니다.
또한 갱신이 진행되면 같은 방법으로 lazy tree에 차곡차곡 수정될 값만 저장해놓음으로써 최적화됩니다.
