SegTreePersistente.cpp

#include <bits/stdc++.h>
using namespace std;

struct Node	{
	int val = 0;
	Node *L = NULL, *R = NULL;
	Node(int v = 0) : val(v), L(NULL), R(NULL) {}
};

Node* build(int l, int r){
	if(l == r) return new Node();

	int m = (l+r)/2;

	Node *node = new Node();

	node->L = build(l,   m);
	node->R = build(m+1, r);
	node->val = node->L->val + node->R->val;

	return node;
}

Node* update(Node *node, int l, int r, int pos, int v){
	if( pos < l || r < pos ) return node;
	if(l == r) return new Node(node->val + v);

	int m = (l+r)/2;

	Node *nw = new Node();

	nw->L = update(node->L, l,   m, pos, v);
	nw->R = update(node->R, m+1, r, pos, v);
	nw->val = nw->L->val + nw->R->val;

	return nw;
}

int query(Node *node, int l, int r, int a, int b){
	if(b <  l || r <  a || node == NULL) return 0;
	if(a <= l && r <= b) return node->val;

	int m = (l+r)/2;

	return query(node->L, l, m, a, b) + query(node->R, m+1, r, a, b);
}

int kth(Node *Left, Node *Right, int l, int r, int k){
	if(l == r) return l;

	int sum = Right->L->val - Left->L->val;
	int m = (l+r)/2;

	if(sum >= k) return kth(Left->L, Right->L, l, m, k);
	return kth(Left->R, Right->R, m+1, r, k - sum);
}

/*LATEX_DESC_BEGIN***************************
-> **Segment Tree Persistente**
Build(1, N) -> Cria uma Seg Tree completa de tamanho N;	RETORNA um *Ponteiro pra Raíz
Update(Root, 1, N, pos, v) 	-> Soma +V na posição POS; RETORNA um *Ponteiro pra Raíz da nova versão;
Query(Root, 1, N, a, b) 	-> RETORNA o valor calculado no range [a, b];
Kth(RootL, RootR, 1, N, K) 	-> Faz uma Busca Binária na Seg; Mais detalhes abaixo;
[ Root -> Nó Raiz da Versão da Seg na qual se quer realizar a operação ]
Para guardar as Raízes, use: vector<Node*> roots

Build:  O(N) !!! Sempre chame o Build
Query:  O(log N)
Update: O(log N)
Kth:	O(Log N)

Comportamento do K-th(SegL, SegR, 1, N, K):
	-> Retorna índice da primeira posição i cuja soma de prefixos [1, i] é >= k 
	na Seg resultante da subtração dos valores da (Seg R) - (Seg L).
	-> Pode ser utilizada para consultar o K-ésimo menor valor no intervalo [L, R] de um array. 
	A Seg deve ser utilizada como um array de frequências. Comece com a Seg zerada (Build). 
	Para cada valor V do Array chame um update(roots.back(), 1, N, V, 1) e guarde o ponteiro da seg.
	Consultar o K-ésimo menor valor de [L, R]: chame kth(roots[L-1], roots[R], 1, N, K);
*****************************LATEX_DESC_END*/