index tree에서 구간 update를 어찌 하나요?

요새 문제를 풀다보면 자꾸 구간 update를 요구해서 자꾸 심기를 불편하게 하네요.

만약 [4 8]구간을 업데이트한다고 하면

[4 8], [4 6], [7 8], [4 5], [6 6], [7 7], [8 8], [4 4]

에 해당하는 모든 node를 업데이트 해야 하는데, 그러면

구간 업데이트 하는데 구간의 크기만큼의 시간이 걸린다면 index tree를 사용하는 의미가 없어지더라고요..

그래서 유명한 mars map문제 해설 등을 봤는데,

해당 구간만 update하고 그 아래 node로는 내려가지 않더라고요.

그럼 [4 8]구간을 업데이트 하고 나중에 쿼리로 [6 10]구간을 요구하면 문제가 생기지 않을까 합니다.

제가 생각하기에 구간 업데이트가 필요하다고 생각되는 문제를 올려봅니다.

http://acm.pku.edu.cn/JudgeOnline/problem?id=3580

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4108

http://acm.pku.edu.cn/JudgeOnline/problem?id=3657

http://acm.pku.edu.cn/JudgeOnline/problem?id=3667

http://acm.pku.edu.cn/JudgeOnline/problem?id=3580

답변 부탁드립니다 ! ^^