[Algorithm] Segment Tree 구현
세그먼트 트리를 구조체로 구현하면 정말 깔끔해진다. 무한 자기참조를 위해 남겨 놓는다. Maximum 세그먼트 트리를 구현한 소스를 남긴다.
#include<bits/stdc++.h>
using namespace std;
struct Node
{
Node *l, *r;
int s,e;
int v;
Node(int s,int e) : l(NULL), r(NULL), s(s), e(e), v(0){}
~Node(){if(l) delete l; if(r) delete r;}
} *root;
void init(Node *node, int* arr)
{
if(node->s == node->e)
{
node->v = arr[node->s];
return;
}
int mid = (node->s + node->e)/2;
node->l = new Node(node->s, mid);
init(node->l, arr);
node->r = new Node(mid+1, node->e);
init(node->r, arr);
node->v = max(node->l->v, node->r->v);
}
void update(Node *node, int x, int v)
{
if(node->e < x or x < node->s) return;
if(node->s == node->e)
{
node->v = v;
return;
}
update(node->l, x,v); update(node->r, x,v);
node->v = max(node->l->v, node->r->v);
}
int query(Node *node, int a,int b)
{
if(a <= node->s and node->e <= b) return node->v;
if(b < node->s or node->e < a) return -1;
return max(query(node->l, a,b), query(node->r, a,b));
}
void printS(Node* node)
{
printf("(%d %d %d) ", node->s,node->e, node->v);
if(node->l) printS(node->l);
if(node->r) printS(node->r);
}
int main()
{
int arr[] = {0,1,2,3,4,5,6,7,8,9,10,11,12};
root = new Node(1,10);
init(root, arr);
printf("%d ", query(root,3,5));
update(root, 5, 15);
printf("%d", query(root,3,7));
delete root;
}
Comments ()