1. ๊ฐ๋ ๐ซ
์ธ๊ทธ๋จผํธ ํธ๋ฆฌ(Segment Tree)๋ ์ฌ๋ฌ ๊ฐ์ ๋ฐ์ดํฐ๊ฐ ์กด์ฌํ ๋ ํน์ ๊ตฌ๊ฐ์ ํฉ์ ๊ตฌํ๋ ๋ฐ ์ฌ์ฉํ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
ํธ๋ฆฌ ์ข ๋ฅ ์ค ํ๋๋ก ์ด์งํธ๋ฆฌ์ ํํ์ด๋ฉฐ, ํน์ ๊ตฌ๊ฐ์ ํฉ์ ๊ฐ์ฅ ๋น ๋ฅด๊ฒ ๊ตฌํ ์ ์๋ค๋ ์ฅ์ ์ด ์๋ค. O(log N)
2. ๋์๋ฐฉ์ ๐
์ธ๊ทธ๋จผํธ ํธ๋ฆฌ๋ฅผ ์ด์ฉํ๊ธฐ ์ํด์๋ ์ฐ์ '๊ตฌ๊ฐ ํฉ ํธ๋ฆฌ'๋ฅผ ์์ฑํด์ผ ํ๋ค. ๊ทธ๋ฆฌ๊ณ '๊ตฌ๊ฐ ํฉ์ ๊ตฌํ๋ ํจ์'์ '์์๋ฅผ ์์ ํ๋ ํจ์'๋ฅผ ์ด์ฉํ์ฌ ๊ตฌ๊ฐ ํฉ์ ๊ตฌํ๊ณ ํน์ ์์๋ฅผ ์์ ํ ์ ์๋ค.
'1 9 3 8 4 5 5 9 10 3 4 5'๋ผ๋ 12๊ฐ์ ์์๋ฅผ ๊ฐ์ง ๋ฐฐ์ด์ด ์ฃผ์ด์ก์ ๋ ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ๋ฅผ ์ด์ฉํ์ฌ ๊ตฌ๊ฐ ํฉ์ ๊ตฌํด๋ณด์.
1. ๊ตฌ๊ฐ ํฉ ํธ๋ฆฌ ์์ฑํ๊ธฐ
'๊ตฌ๊ฐ'์ ์๋ ๋ฐ์ดํฐ ๋ฒ์๋ฅผ ๋ฐ์ฉ ๋ถํ ํ๋ ๊ฒ์ผ๋ก ์ค์ ํ๋ค. ์ต์๋จ ๋ ธ๋๋ ์ ์ฒด ์์๋ฅผ ํฌํจํ๋ ๊ตฌ๊ฐ์ธ 0~11๋ก ์ค์ ๋๋ค. ์ต์๋จ ๋ ธ๋์ ์ผ์ชฝ ์์์ 0~5, ์ค๋ฅธ์ชฝ ์์์ 6~11์ ๊ตฌ๊ฐ์ ๊ฐ์ง๋ค.
์ด๋ฅผ ๊ทธ๋ฆผ์ผ๋ก ํํํ๋ฉด ๋ค์๊ณผ ๊ฐ์ ๊ตฌ๊ฐ์ ๊ฐ์ง๊ฒ ๋๋ค. (์ฌ๊ธฐ์๋ ๋ ธ๋์ ๊ฐ์ ํํํ ๊ฒ ์๋๋ผ ๊ตฌ๊ฐ์ ํ์ํ ๊ฒ์ด๋ค.)
๊ตฌ๊ฐ ํฉ ํธ๋ฆฌ์ ์์ ๊ฐ์๋ 32๊ฐ์ฌ์ผ ํ๋ค. ์ด๋ฅผ ๊ฐ๋จํ ์ ์ ์๋ ๋ฐฉ๋ฒ์ ๋ฐ์ดํฐ์ ๊ฐ์๊ฐ N(=12) ๊ฐ ์ผ ๋ N๋ณด๋ค ํฐ ์ ๊ณฑ์(= 16)๋ฅผ 2๋ฐฐ ํ ๊ฒ(=32)์ด๋ค. ๋ ๊ฐ๋จํ๊ฒ๋ ๋ฐ์ดํฐ์ ๊ฐ์ N(=12)์ 4๋ฅผ ๊ณฑํ ๊ฐ(=48)์ ๋ฐฐ์ด์ ํฌ๊ธฐ๋ก ํ ๋นํด ๋์ผ๋ฉด ๋๋ค.
๊ฐ๊ฐ์ ๋ ธ๋ ๊ฐ๋ค์ ๋ ธ๋์ ๊ตฌ๊ฐ์ ์ํ ์์๋ค์ ํฉ์ ๋ํ๋ธ๋ค.
์ด๋ฅผ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ ์ฌ๊ท๋ฅผ ์ด์ฉํ ์ ์๋ค.
static int init(int startIdx, int endIdx, int nodeIdx) {
// ์๊ธฐ ์์ ๋ง์ ์์๋ก ๊ฐ์ง๋ ๊ตฌ๊ฐ // ๋ ๊ตฌ๊ฐ
if(startIdx == endIdx)
return segTree[nodeIdx] = arr[startIdx];
int mid = (startIdx + endIdx) / 2;
// ์ผ์ชฝ ์์ ๋
ธ๋ ๊ตฌ๊ฐ ํฉ
int leftSum = init(startIdx, mid, nodeIdx * 2);
// ์ค๋ฅธ์ชฝ ์์ ๋
ธ๋ ๊ตฌ๊ฐ ํฉ
int rightSum = init(mid + 1, endIdx, nodeIdx * 2 + 1);
return segTree[nodeIdx] = leftSum + rightSum;
}
2. ๊ตฌ๊ฐ ํฉ์ ๊ตฌํ๋ ํจ์ ๋ง๋ค๊ธฐ
4~8์ ๊ตฌ๊ฐ ํฉ์ ๊ตฌํ๋ค๊ณ ํ์. ๊ทธ๋ฌ๋ฉด ์๋์ ์ธ ๋ ธ๋์ ๊ฐ๋ง ๋ํด์ฃผ๋ฉด ๋๋ค.
ํด๋น ๋ ธ๋๋ค์ ์ป๊ธฐ ์ํด์๋ 3๊ฐ์ง ๊ฒฝ์ฐ๊ฐ ์กด์ฌํ๋ค. ์ฐพ๊ณ ์ ํ๋ ๊ตฌ๊ฐ์ ํ๊ฒ ๊ตฌ๊ฐ์ด๋ผ๊ณ ํ์.
- ํ์ํ๋ ๊ตฌ๊ฐ์ด ํ๊ฒ ๊ตฌ๊ฐ์ ํฌํจ๋๋ ๊ฒฝ์ฐ
ํด๋น ๋ ธ๋ ๊ฐ์ ๊ฐ์ ธ์จ๋ค. - ํ์ํ๋ ๊ตฌ๊ฐ์ด ํ๊ฒ ๊ตฌ๊ฐ์ ํฌํจ๋์ง ์๋ ๊ฒฝ์ฐ
๋ ์ด์ ํ์ํ์ง ์๋๋ค. - ํ์ํ๋ ๊ตฌ๊ฐ์ด ํ๊ฒ ๊ตฌ๊ฐ์ ์ผ๋ถ๋ถ ํฌํจ๋๋ ๊ฒฝ์ฐ
์์ ๋ ธ๋๋ค์ ๊ตฌ๊ฐ์ ๋ค์ ์ดํด๋ณด๋ฉด์ 1๋ฒ๊ณผ 2๋ฒ์ ๊ฒฝ์ฐ์ ํด๋นํ ๋๊น์ง ํ์ํ๋ค.
์ด๋ฅผ ์ฝ๋๋ก ํํํ๋ฉด ์๋์ ๊ฐ๋ค.
// ๊ตฌํ๊ณ ์ ํ๋ ๊ตฌ๊ฐ : left ~ right
static int sum(int startIdx, int endIdx, int nodeIdx, int left, int right) {
// ๊ตฌ๊ฐ์ ๋ฒ์ด๋๋ ๊ฒฝ์ฐ
if(left > endIdx || right < startIdx)
return 0;
// ๊ตฌ๊ฐ์ ํฌํจ๋๋ ๊ฒฝ์ฐ
if(left <= startIdx && endIdx <= right)
return segTree[nodeIdx];
// ๊ตฌ๊ฐ์ ๊ฑธ์น๋ ๊ฒฝ์ฐ
// ์์ ๋
ธ๋๋ก ์ง์
ํ์ฌ ๊ตฌ๊ฐ์ ์ํ๋ ๊ฒ๋ง ์ฐพ๊ธฐ
int mid = (startIdx + endIdx) / 2;
int leftRangeSum = sum(startIdx, mid, nodeIdx * 2, left, right);
int rightRangeSum = sum(mid + 1, endIdx, nodeIdx * 2 + 1, left, right);
return leftRangeSum + rightRangeSum;
}
3. ํน์ ์์์ ๊ฐ์ ์์ ํ๋ ํจ์ ๋ง๋ค๊ธฐ
ํน์ ์์์ ๊ฐ์ ์์ ํ๋ค๊ณ ํ๋ฉด ํด๋น ์์๋ฅผ ํฌํจํ๊ณ ์๋ ๊ตฌ๊ฐ์ ๋ ธ๋๋ค์ ๋ชจ๋ ์ ๋ฐ์ดํธํด ์ฃผ๋ฉด ๋๋ค. ์๋ฅผ ๋ค์ด 3๋ฒ ์ธ๋ฑ์ค์ ๊ฐ์ ์์ ํ๋ค๊ณ ํ๋ฉด ์๋ ํ์๋ ๋ ธ๋๋ค์ ๋ชจ๋ ์ ๋ฐ์ดํธํด์ค์ผ ํ๋ค. (๋๊ทธ๋ผ๋ฏธ ์์๋ ๊ตฌ๊ฐ์ ๋ฒ์๋ฅผ ํ์ํ ๊ฒ์ด๋ค.)
์ด๋ฅผ ์ฝ๋๋ก ํํํ๋ฉด ์๋์ ๊ฐ๋ค.
static void update(int startIdx, int endIdx, int nodeIdx, int targetIdx, int diff) {
// ๊ตฌ๊ฐ์ ๋ฒ์ด๋๋ ๊ฒฝ์ฐ
if(targetIdx < startIdx || targetIdx > endIdx)
return;
// ๊ตฌ๊ฐ์ ์ํ๋ ๊ฒฝ์ฐ(diff์ ์ํฅ์ ๋ฐ๋ ๊ฒฝ์ฐ)
// diff(๊ธฐ์กด๊ฐ๊ณผ ์๋ก์ด ๊ฐ์ ์ฐจ์ด)๋ฅผ ๋ํด์ฃผ๊ธฐ
segTree[nodeIdx] += diff;
// leaf ๋
ธ๋์ธ ๊ฒฝ์ฐ
if(startIdx == endIdx)
return;
// ์์ ํ๊ณ ์ ํ๋ ๋
ธ๋๋ฅผ ์ฐพ์ง ๋ชปํ๊ธฐ ๋๋ฌธ์
// targetIdx๋ฅผ ์ฐพ๊ธฐ์ํด ์์๋
ธ๋๋ก ๋ด๋ ค๊ฐ์ผ ํจ
int mid = (startIdx + endIdx) / 2;
update(startIdx, mid, nodeIdx * 2, targetIdx, diff);
update(mid + 1, endIdx, nodeIdx * 2 + 1, targetIdx, diff);
}
3. ๊ตฌํ(JAVA) ๐
static int[] arr = {1, 9, 3, 8, 4, 5, 5, 9, 10, 3, 4, 5};
static int cnt = arr.length;
static int[] segTree = new int[4 * cnt];
public static void main(String[] args) {
init(0, cnt - 1, 1);
// 0๋ถํฐ 12๊น์ง์ ๊ตฌ๊ฐ ํฉ(์ ์ฒด ๊ตฌ๊ฐ)
System.out.println(sum(0, cnt - 1, 1, 0, 12)); // 66
// 4๋ถํฐ 8๊น์ง์ ๊ตฌ๊ฐ ํฉ(์ ์ฒด ๊ตฌ๊ฐ)
System.out.println(sum(0, cnt - 1, 1, 4, 8)); // 33
// 3๋ฒ ์ธ๋ฑ์ค์ ๊ฐ์ 8์์ 7๋ก ์์ (diff = -6)
update(0, cnt - 1, 1, 3, -6);
// ๋ณ๊ฒฝ ํ : 0~2 ๊ตฌ๊ฐํฉ
// ๋ณํX
System.out.println(sum(0, cnt - 1, 1, 0, 2)); // 13
// ๋ณ๊ฒฝ ํ : ์ ์ฒด ๊ตฌ๊ฐํฉ
// ๋ณํO (66 -> 60)
System.out.println(sum(0, cnt - 1, 1, 0, 12)); // 60
}
// 1. ๊ตฌ๊ฐ ํฉ ํธ๋ฆฌ ์์ฑํ๊ธฐ
static int init(int startIdx, int endIdx, int nodeIdx) {
// ์๊ธฐ ์์ ๋ง์ ์์๋ก ๊ฐ์ง๋ ๊ตฌ๊ฐ // ๋ ๊ตฌ๊ฐ
if(startIdx == endIdx)
return segTree[nodeIdx] = arr[startIdx];
int mid = (startIdx + endIdx) / 2;
// ์ผ์ชฝ ์์ ๋
ธ๋ ๊ตฌ๊ฐ ํฉ
int leftSum = init(startIdx, mid, nodeIdx * 2);
// ์ค๋ฅธ์ชฝ ์์ ๋
ธ๋ ๊ตฌ๊ฐ ํฉ
int rightSum = init(mid + 1, endIdx, nodeIdx * 2 + 1);
return segTree[nodeIdx] = leftSum + rightSum;
}
// 2. ๊ตฌ๊ฐ ํฉ์ ๊ตฌํ๋ ํจ์ ๋ง๋ค๊ธฐ
// ๊ตฌํ๊ณ ์ ํ๋ ๊ตฌ๊ฐ : left ~ right
static int sum(int startIdx, int endIdx, int nodeIdx, int left, int right) {
// ๊ตฌ๊ฐ์ ๋ฒ์ด๋๋ ๊ฒฝ์ฐ
if(left > endIdx || right < startIdx)
return 0;
// ๊ตฌ๊ฐ์ ํฌํจ๋๋ ๊ฒฝ์ฐ
if(left <= startIdx && endIdx <= right)
return segTree[nodeIdx];
// ๊ตฌ๊ฐ์ ๊ฑธ์น๋ ๊ฒฝ์ฐ
// ์์ ๋
ธ๋๋ก ์ง์
ํ์ฌ ๊ตฌ๊ฐ์ ์ํ๋ ๊ฒ๋ง ์ฐพ๊ธฐ
int mid = (startIdx + endIdx) / 2;
int leftRangeSum = sum(startIdx, mid, nodeIdx * 2, left, right);
int rightRangeSum = sum(mid + 1, endIdx, nodeIdx * 2 + 1, left, right);
return leftRangeSum + rightRangeSum;
}
// 3. ํน์ ์์์ ๊ฐ์ ์์ ํ๋ ํจ์ ๋ง๋ค๊ธฐ
static void update(int startIdx, int endIdx, int nodeIdx, int targetIdx, int diff) {
// ๊ตฌ๊ฐ์ ๋ฒ์ด๋๋ ๊ฒฝ์ฐ
if(targetIdx < startIdx || targetIdx > endIdx)
return;
// ๊ตฌ๊ฐ์ ์ํ๋ ๊ฒฝ์ฐ(diff์ ์ํฅ์ ๋ฐ๋ ๊ฒฝ์ฐ)
// diff(๊ธฐ์กด๊ฐ๊ณผ ์๋ก์ด ๊ฐ์ ์ฐจ์ด)๋ฅผ ๋ํด์ฃผ๊ธฐ
segTree[nodeIdx] += diff;
// leaf ๋
ธ๋์ธ ๊ฒฝ์ฐ
if(startIdx == endIdx)
return;
// ์์ ํ๊ณ ์ ํ๋ ๋
ธ๋๋ฅผ ์ฐพ์ง ๋ชปํ๊ธฐ ๋๋ฌธ์
// targetIdx๋ฅผ ์ฐพ๊ธฐ์ํด ์์๋
ธ๋๋ก ๋ด๋ ค๊ฐ์ผ ํจ
int mid = (startIdx + endIdx) / 2;
update(startIdx, mid, nodeIdx * 2, targetIdx, diff);
update(mid + 1, endIdx, nodeIdx * 2 + 1, targetIdx, diff);
}
4. ์๊ฐ๋ณต์ก๋ ๐ธ
๊ตฌ๊ฐ ํฉ ํธ๋ฆฌ๋ฅผ ์์ฑํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ O(N log N)์ด๋ค.
๊ทธ๋ฆฌ๊ณ ๊ตฌ๊ฐ ํฉ์ ๊ตฌํ๊ฑฐ๋ ๊ฐ์ ๊ฒฝ์ ํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ํธ๋ฆฌ ๊ตฌ์กฐ์ ํน์ฑ์ ์ด์ฉํ๊ธฐ ๋๋ฌธ์ O(log N)์ด๋ค.
ํด๋น ๊ธ์
๋๋๋น ๋์ '41. ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ(Segment Tree)',
pseong ๋์ '์ธ๊ทธ๋จผํธ ํธ๋ฆฌ(๊ตฌ๊ฐ ํธ๋ฆฌ), ๋๋ฆฌ๊ฒ ๊ฐฑ์ ๋๋ ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ(Lazy Propagation)'
๋ฅผ ์ฐธ๊ณ ํ์์ต๋๋ค.
'๐ ์๋ฃ๊ตฌ์กฐ > ํธ๋ฆฌ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๋ฃ๊ตฌ์กฐ] ํ(Heap) (0) | 2023.03.10 |
---|