[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;
}