uang's blog

"구간 합" 유형 + 값 수정 쿼리 가 있는 문제는 "세그먼트 트리" 를 이용해 풀어야 한다.

구간 합은 보통 prefix sum(psum) 배열을 이용해 [a, b] 의 구간합을 psum[b] - psum[a-1] 로 풀 수 있다.

하지만 구간 값이 변경되는 "K 개의 수정 쿼리"가 있을 때는, 매 수정마다 N 크기의 배열을 다시 계산해야하기 때문에,

전체 복잡도가 O(K*N) 이 된다.

세그먼트 트리는 

     Leaf node      : 배열 값

     Internal node : 자식노드들의 구간 합

을 저장하여, 수정을 O(logN) 만에, 구간 합 계산 또한 O(logN) 번 만에 수행할 수 있는 자료구조이다.

자세한 내용은 백준님 블로그에 설명되어 있다.

이 문제는 값 수정 쿼리가 있는 구간 곱을 계산하는 문제로, 세그먼트 트리를 이용해야하며, 합 대신 곱 연산으로 변경해주면 된다.

#주의할 점

* 곱 연산이기 때문에 발생하는 오버플로우 문제가 있다.

* update 를 하는 방식은 다양하지만, 이전 값과의 차이(difference) 값을 해당 노드마다 곱해주는 방식으로는 WA 를 받는다.

  - difference 값을 계산하면서 발생하는 나눗셈 연산이 문제의 조건인 1000000007 MOD 연산에 영향을 줄 수 있을 것 같다.

  - 따라서 잎 노드의 변경으로부터 다시 계산하는 방식으로 업데이트를 수행한다.

소스코드

1. #include<stdio.h>
2. #include<vector>
3. #define MOD(x) ((x)%1000000007)
4. using namespace std;
5. typedef unsigned long long ull;
6. int n, m, k;
7. ull arr[1000001];
8.  
9. ull make_seg_tree(vector< ull > &v, int node, int start, int end){
10. if(start == end){
11. return v[node] = arr[start];
12. }
13. return v[node] = MOD( make_seg_tree(v, node*2, start, (start+end)/2) *
14. make_seg_tree(v, node*2+1, (start+end)/2 + 1, end));
15. }
16. ull update_seg_tree(vector<ull>&v, int node, int start, int end, int idx, ull val, bool was_zero) {
17. if( idx < start || end < idx) return v[node];
18.  
19. if(start == end) {
20. arr[idx] = val;
21. return v[node] = val;
22. } else {
23. return v[node] = MOD(update_seg_tree(v, node*2, start, (start+end)/2, idx, val, was_zero) *
24. update_seg_tree(v, node*2+1, (start+end)/2+1, end, idx, val, was_zero));
25. }
26. // v[node] = was_zero ? val : MOD((ull)(v[node] / arr[idx] * val)); // difference 를 이용한 수정
27. }
28.  
29. ull get_mul(vector< ull >&v, int node, int start, int end, int left, int right) {
30. if(right < start || end < left) return 1;
31. if(start==end) return v[node];
32. if(left <= start && end <= right){
33. return v[node];
34. }
35. return MOD( get_mul(v, node*2, start, (start+end)/2, left, right) *
36. get_mul(v, node*2+1, (start+end)/2+1, end, left, right));
37. }
38.  
39. int main(){
40. scanf("%d %d %d",&n,&m,&k);
41. for(int i=1;i<=n;i++){
42. scanf("%u",&arr[i]);
43. }
44. vector< ull > v(4*n);
45. make_seg_tree(v, 1, 1, n);
46.  
47. int a, b,c;
48. for(int i=0; i<m+k;i++){
49. scanf("%d %d %d",&a, &b, &c);
50. if(a == 1){
51. //update
52. bool was_zero = arr[b] == 0;
53. ull val = (ull)c;
54. update_seg_tree(v, 1, 1, n, b, val, was_zero);
55. arr[b] = val;
56. } else{
57. //get mul
58. printf("%u\n", get_mul(v, 1, 1, n, b, c));
59. }
60. }
61.  
62. return 0;
63. }