Segment Tree (세그먼트 트리)

RMQ(Range Minimum/Maximum Query) : 구간 최소/최대 쿼리 문제를 해결할 때 사용

코드

#include <stdio.h>
#include <algorithm>

using namespace std;

typedef struct Node {
    int a, b, idx;
} Node;

int n, tre[103 << 2];
Node a[103];

bool compare(Node a, Node b)
{
    return a.a < b.a;
}

bool compare2(Node a, Node b)
{
    return a.b < b.b;
}

int query(int l, int r, int node, int start, int end)
{
    if (r < start || l > end)
        return 0;
    if (start <= l && r <= end)
        return tre[node];

    int mid = (l + r) / 2;
    return max(query(l, mid, node * 2, start, end), query(mid + 1, r, node * 2 + 1, start, end));
}

int update(int l, int r, int node, int idx, int val)
{
    if (r < idx || l > idx)
        return tre[node];
    if (l == r)
        return tre[node] = val;

    int mid = (l + r) / 2;
    return tre[node] = max(update(l, mid, node * 2, idx, val), update(mid + 1, r, node * 2 + 1, idx, val));
}


int main()
{
    int i, j, k;
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        scanf("%d%d", &j, &k);
        a[i].a = j;
        a[i].b = k;
    }

    sort(a + 1, a + 1 + n, compare);

    for (i = 1; i <= n; i++)
        a[i].idx = i;

    sort(a + 1, a + 1 + n, compare2);

    for (i = 1; i <= n; i++) {
        if (a[i].idx == 5)
            i = i;
        int cnt = query(1, n, 1, 1, a[i].idx);
        update(1, n, 1, a[i].idx, cnt + 1);
    }

    printf("%d", n - query(1, n, 1, 1, n));

    return 0;
}

전깃줄(https://www.acmicpc.net/problem/2565) - 구간합 사례 (n 보다 작은 수가 몇개 있었는가 -> LIS)

#include <stdio.h>
#include <queue>
#define MAX 65535

using namespace std;

typedef long long int lld;

int tre[70000 << 2];

int update(int l, int r, int node, int pos, int diff) {
    if (pos < l || r < pos)
        return tre[node];
    if (l == r)
        return tre[node] += diff;
    int mid = (l + r) / 2;
    return tre[node] = update(l, mid, node * 2, pos, diff) + update(mid + 1, r, node * 2 + 1, pos, diff);
}

int kth(int l, int r, int k, int node) {
    if (l == r)
        return l;
    int mid = (l + r) / 2;
    if (tre[node * 2] >= k)
        return kth(l, mid, k, node * 2);
    else
        return kth(mid + 1, r, k - tre[node * 2], node * 2 + 1);
}

int main()
{
    int n, k, i, j;
    queue<int> q;
    lld result = 0;

    scanf("%d%d", &n, &k);
    for (i = 1; i <= n; i++) {
        scanf("%d", &j);
        q.push(j);
        update(0, MAX, 1, j, 1);
        if (q.size() == k) {
            result += kth(0, MAX, (k + 1) / 2, 1);
            update(0, MAX, 1, q.front(), -1);
            q.pop();
        }
    }

    printf("%lld", result);
    return 0;
}

중앙값 측정 (https://www.acmicpc.net/problem/9426 - 구간합 + kth 구현 사례

정리

포화이진트리로 표현, n << 2 만큼의 메모리 필요
초기화(build) : O(N)
질의(query) : O(logN)
- 트리 탐색 구간과 조회하려는 위치의 교집합에 따라 다음의 처리를 한다
  - 공집합 : 생각하지 않는다
  - 탐색구간 : 그대로 반환
  - 이외의 경우 : 자식들 중에서 최적의 답을 반환
- 이외에도 트리의 성질을 활용해서 1...node 까지의 합이 k 가 되는 지점을 검색할 수 있다
  - 순열 문제(1849)
업데이트(update) : O(logN)
- 왼쪽 자식이 업데이트 노드를 포함 : 왼쪽 업데이트 호출
- 오른쪽 자식이 업데이트 노드를 포함 : 오른쪽 업데이트 호출
- 자식들을 통해 현재 노드에 대한 값을 업데이트
Query 의 종류 : max, min, sum, xor, nth(몇 번째), list(merge sort tree)
범위 검색 및 업데이트를 할 경우 lazy propagation 을 사용한다, O((logN)^2)
- Lazy Propagation 문서로 이동
직사각형 면적의 합을 구하는 문제는 plane sweeping + segment tree 를 이용하여 풀 수 있다
- http://codedoc.tistory.com/421
- http://59.23.150.58/30stair/plane_sweeping_doc/plane_sweeping_doc.php?pname=plane_sweeping_doc

Segment Tree

Segment Tree (세그먼트 트리)

코드

정리

관련 문제

참고 자료

results matching ""

No results matching ""