[LeetCode/C#/Segment Tree] 6/19 Range Sum Query - Mutable 문제 풀이

https://leetcode.com/problems/range-sum-query-mutable/

문제 출처 사이트 : 

Range Sum Query - Mutable - LeetCode

1. 문제 Summary

주어진 정수 array에서 (1)특정 범위를 Sum하는 함수와 (2)array의 특정 index를 Update하는 함수를 맹글어라.

Input ["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]

Output [null, 9, null, 8]

 

 

2. 문제 풀이

단순히 Time Complexity O(N)으로 풀이하였을 때 15개 case에서 13번째 case에서 막혔다.

더 빠른 알고리즘이 적용되어야 하는데 머리가 텅텅빈 나는 더이상 풀이할 수 없어서 Leetcode에서 제공하는 Solution을 참고하여 공부하는데 의의를 두었다.

https://leetcode.com/problems/range-sum-query-mutable/solution/

Range Sum Query - Mutable - LeetCode

(더 많은 풀이들이 설명되어 있다.)

 

풀이 방법 : Segment Tree

데이터가 연속적으로 존재할 때, 특정 범위의 데이터 합을 구하고자 함.

 

public class NumArray {
    private int[] tree;
    private int n;
    
    public NumArray(int[] nums) {
        this.n = nums.Length;
        this.tree = new int[n*2];
        
        for(int i = n; i < 2*n; i++){
            this.tree[i] = nums[i - n];

        }
        for(int i=n-1; i > 0; --i){
            this.tree[i] = this.tree[i*2] + this.tree[i*2+1];
        }
    }

 

/* =========================================================

NumArray 설명 : Time Complexity O(N)

Tree array 만들어주기

========================================================= */    
    public void Update(int index, int val) {
        index = index + this.n;
        this.tree[index] = val;
        while(index > 0){
            int left = index;
            int right = index;
            if(index%2 == 0){
                right = index + 1;
            }
            else{
                left = index - 1;
            }
            this.tree[index/2] = this.tree[left] + this.tree[right];
            index /= 2;
        }
    }
    

/* ==========================================================

public void Update 설명 : Time Complexity O(logN)

Update 함수 예시

========================================================== */

    public int SumRange(int left, int right) {
        int sum = 0;
        left = left + this.n;
        right = right + this.n;
        while(left<=right){
            if(left % 2 == 1){
                sum += this.tree[left];
                left += 1;
            }
            if(right % 2 == 0){
                sum += this.tree[right];
                right -= 1;
            }
            left /= 2;
            right /= 2;
        }
        return sum;
    }

/* ==========================================================

public int SumRange 설명 : Time Complexity O(logN)

SumRange 예시

========================================================== */
}