-
[LeetCode/C#/Segment Tree] 6/19 Range Sum Query - Mutable 문제 풀이프로그래밍/LeetCode 2021. 6. 19. 16:27728x90
https://leetcode.com/problems/range-sum-query-mutable/
문제 출처 사이트 :
Range Sum Query - Mutable - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
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
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
(더 많은 풀이들이 설명되어 있다.)
풀이 방법 : 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 예시 ========================================================== */
}728x90'프로그래밍 > LeetCode' 카테고리의 다른 글
[LeetCode/Python/Disjoint Sets] 6/25 Redundant Connection 풀이 (0) 2021.06.26 [LeetCode/Python] 6/21 Pascal’s Triangle 문제 풀이 (0) 2021.06.22