leetcode: Range Sum Query - Mutable

세그먼트 트리란?

주어진 쿼리에 대해 빠르게 응답하기 위해 만들어진 자료구조로, 주로 구간 합을 다룰 때 많이 사용한다.

대부분 완전 이진 트리로 구성된다.

 

세그먼트 트리에서는

수를 바꾸는 과정 :: O(lgN)

수를 더하는 과정 :: O(lgN)으로 변하게 된다.

M번 실행한다 치면 O(MlgN + MlgN) -> O(MlgN)이 걸리게 된다.

 

 

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

class NumArray {
	int[] tree;
	int n;

	public NumArray(int[] nums) {
		if (nums.length > 0) {
			n = nums.length;
			tree = new int[n * 2];
			buildTree(nums);
		}
	}

	private void buildTree(int[] nums) {
		for (int i = n, j = 0; i < 2 * n; i++, j++)
			tree[i] = nums[j];
		for (int i = n - 1; i > 0; --i)
			tree[i] = tree[i * 2] + tree[i * 2 + 1];
	}

	void update(int pos, int val) {
		pos += n;
		tree[pos] = val;
		while (pos > 0) {
			int left = pos;
			int right = pos;
			if (pos % 2 == 0) {
				right = pos + 1;
			} else {
				left = pos - 1;
			}

			tree[pos / 2] = tree[left] + tree[right];
			pos /= 2;
		}
	}

	public int sumRange(int l, int r) {
		l += n;
		r += n;
		int sum = 0;
		while (l <= r) {
			if ((l % 2) == 1) {
				sum += tree[l];
				l++;
			}
			if ((r % 2) == 0) {
				sum += tree[r];
				r--;
			}
			l /= 2;
			r /= 2;
		}
		return sum;
	}
}

세그먼트 트리에 대해 좀 더 공부해 봐야겠다...