정답이 범위 내에 있다는 보장이 있다면 중간합이 오버플로우가 나도 문제는 없다고 생각합니다.
질문자께서 보이신 예시를 생각하면 (-2^63) + (-2^63)을 계산하면 0으로 원래 정답보다 2^64 크게 나오게 되지만 역시 (2^63 - 1) + 1을 계산하면 -2^63으로 원래 답보다 2^64만큼 작게 나오게 되기 때문에 총합은 그냥 64비트 정수 덧셈으로 구해도 똑같이 나옵니다.
즉 정답이 범위 내에 나온다는 보장이 있다면 중간에 오버플로우가 나더라도 앞의 보장으로 인해 다시 오프셋이 맞춰질 것이라고 보고 해결하셔도 될 것 같습니다.
다만 이는 문제가 정답 범위를 보장했기 때문에 가능한 풀이겠네요.

hinoky 9달 전 1
풀이과정을 대충 떠올리긴 했는데,
입력값 제한이 64비트 정수범위인 거 외 다른 제한이 없고, 모듈러 연산 하라는 말도 없어서 손도 못대고 있습니다..
입력값중에 -2^63만 없었어도 어찌어찌 모듈러로 구해볼 수 있을 거 같은데
쟤때문에 모듈러연산으로도 못구하고 있어요..
근데 질문게시판 읽어보니깐 다들 세그트리 기초문제라고 하는데
듣도보도 못한 오버플로우 예외처리까지 요구하는 게 좀 이상해서 질문드립니다.
bigint나 int128동원하시나요? 아니면 정수를 이진수로 바꿔서 비트연산 하시나요?
그것도 아니면 세그트리라는 알고리즘 자체에 중간합이 오버플로우 나더라도 결과합은 멀정하게 나오게 설계된 건가요?
제가 생각한 알고리즘은
1. 배열완전이진트리 생성
2. 리프노드에 입력된 배열 넣고 부모노드에 자식배열의 합 넣기 O(n)
3. 변경일 때 리프노드 값 변경하고 따라 올라가면서 부모노드 값 변경하기O(mlogn)
4. 호출일 땐 앞서 트리에서 구간합[1,종료값], 구간합[1,시작값-1]을 구하고 두 수를 빼서 출력하기O(klogn)
입니다
만약 배열이
-2^63 // -2^63 // 2^63-1 // 1이라면 구간합 [1,4] 값이 -2^63으로 64비트 범위 내지만, 트리 만드는 과정에서 오버플로우가 발생하죠.