Notas sobre Árvores de Segmento Persistentes
Estudo baseado em: Resumo de Árvores de Segmento Persistentes
Problema do k-ésimo Menor em Intervalo Estático
P3834 【Modelo】Árvore de Segmento Persistente 2 (Árvore do Presidente)
Descrição
Dada uma sequência, para cada consulta, determinar o k-ésimo menor valor em um intervalo especificado.
Abordagem
Modelo de árvore de segmento persistente.
Considere o caso mais simples, onde o intervalo de consulta é fixo. Primeiramente, discretizamos os dados e utilizamos uma árvore de segmento para mantê-los. Cada nó corresponde ao total de números no domínio de valores discretizados. Durante a consulta de cima para baixo, comparamos o tamanho do filho esquerdo do nó atual com o ranking k. Se for menor ou igual, continuamos no filho esquerdo; caso contrário, procuramos no filho direito por k-tamanho (este princípio é similar ao kth em árvores balanceadas).
Como manter todos os intervalos? A ideia mais direta seria construir N árvores de segmento, mantendo a situação de cada intervalo [i,i], e usar somas prefixas para implementar todos os intervalos. No entanto, o espaço necessário seria proibitivo.
A árvore de segmento persistente resolve o problema de espaço da seguinte forma: claramente, o intervalo [1,i] difere de [1,i-1] apenas em um valor, então cada novo intervalo requer apenas a criação de logn novos nós.
//P3834 【Modelo】Árvore de Segmento Persistente 2 (Árvore do Presidente)
//Cada árvore de segmento mantém o valor extremo de um intervalo, e seguindo o conceito de persistência,
//cada nova árvore adiciona log nós.
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
struct no
{
int filhoEsq,filhoDir,total;
}arvore[MAXN<<5];
int valores[MAXN],raizes[MAXN],n,m,contador=0;
vector<int> valoresUnicos;
int obterIndice( int k )
{
return lower_bound( valoresUnicos.begin(),valoresUnicos.end(),k )-valoresUnicos.begin()+1;
}
void construir( int &raizAtual,int esq,int dir )
{
raizAtual=++contador; arvore[raizAtual].total=0;
if ( esq==dir ) return;
int meio=(esq+dir)>>1;
construir( arvore[raizAtual].filhoEsq,esq,meio );
construir( arvore[raizAtual].filhoDir,meio+1,dir );
}
void atualizar( int esq,int dir,int &atual,int anterior,int k )
{
arvore[++contador]=arvore[anterior];
atual=contador; arvore[contador].total++;
if ( esq==dir ) return;
int meio=(esq+dir)>>1;
if ( k<=meio ) atualizar( esq,meio,arvore[atual].filhoEsq,arvore[anterior].filhoEsq,k );
else atualizar( meio+1,dir,arvore[atual].filhoDir,arvore[anterior].filhoDir,k );
}
int consultar( int esq,int dir, int x, int y, int k )
{
if ( esq==dir ) return esq;
int meio=(esq+dir)>>1,conta=arvore[arvore[y].filhoEsq].total-arvore[arvore[x].filhoEsq].total;
if ( conta>=k ) return consultar( esq,meio,arvore[x].filhoEsq,arvore[y].filhoEsq,k );
else return consultar( meio+1,dir,arvore[x].filhoDir,arvore[y].filhoDir,k-conta );
}
int main()
{
scanf( "%d%d",&n,&m );
for ( int i=1; i<=n; i++ )
scanf( "%d",&valores[i] ),valoresUnicos.push_back( valores[i] );
sort( valoresUnicos.begin(),valoresUnicos.end() );
valoresUnicos.erase( unique(valoresUnicos.begin(),valoresUnicos.end()),valoresUnicos.end() );
construir( raizes[0],1,n );
for ( int i=1; i<=n; i++ )
atualizar( 1,n,raizes[i],raizes[i-1],obterIndice(valores[i]) );
while ( m-- )
{
int l,r,k; scanf( "%d%d%d",&l,&r,&k );
printf( "%d\n",valoresUnicos[consultar(1,n,raizes[l-1],raizes[r],k)-1] );
}
}
Problema do k-ésimo Menor em Intervalo Dinâmico
P2617 Classificações Dinâmicas
Descrição
Dada uma sequência com n números a₁, a₂, ..., aₙ, suportar duas operações:
Q l r k: Consultar o k-ésimo menor número cujo índice está no intervalo [l,r]C x y: Alterar o valor de aₓ para y
Abordagem
Incorporamos uma árvore de Fenwick em uma árvore de segmento, onde cada nó da árvore de Fenwick é a raiz de uma árvore de segmento, utilizando a árvore de Fanwick para manter somas prefixas.
Para a operação de atualização, dado um índice i, começamos pelo nó correspondente a i na árvore de Fenwick e percorremos para cima, atualizando todas as árvores de segmento encontradas. Reduzimos o valor no intervalo correspondente ao valor antigo em 1 e aumentamos no intervalo correspondente ao novo valor em 1. Isso requer a modificação de log árvores. Para a operação de consulta, primeiro percorremos para cima a partir de l-1 e r, registrando todos os nós encontrados. Ao calcular o tamanho atual, usamos a soma dos filhos esquerdos dos nós obtidos a partir de r (representando o tamanho de [1,r]) menos a soma dos filhos esquerdos dos nós obtidos a partir de l-1 (representando o tamanho de [1,l-1]), resultando no tamanho de [l,r]. Ao mover para os filhos esquerdo/direito, nós movemos log nós simultaneamente.
Código
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
struct ArvoreSegmento
{
int valor,filhoEsq,filhoDir;
}arvore[MAXN*400];
struct Consulta
{
bool tipo; int l,r,k,pos,valor;
}consultas[MAXN];
int n,m,valores[MAXN],raizes[MAXN],tamanho,contadorTotal,tmp[2][20],contagem[2],numeros[N<<1];
char operacao[10];
int baixaBit( int x ) { return x&(-x); }
void modificar( int &p,int esq,int dir,int pos,int val )
{
if ( !p ) p=++contadorTotal;
arvore[p].valor+=val;
if ( esq==dir ) return;
int meio=(esq+dir)>>1;
if ( pos<=meio ) modificar( arvore[p].filhoEsq,esq,meio,pos,val );
else modificar( arvore[p].filhoDir,meio+1,dir,pos,val );
}
void inicializarModificacao( int x,int val )
{
int k=lower_bound( numeros+1,numeros+tamanho+1,valores[x] )-numeros;
for ( int i=x; i<=n; i+=baixaBit(i) )
modificar( raizes[i],1,tamanho,k,val );
}
int consultar( int esq,int dir,int k )
{
if ( esq==dir ) return esq;
int meio=(esq+dir)>>1,soma=0;
for ( int i=1; i<=contagem[1]; i++ )
soma+=arvore[arvore[tmp[1][i]].filhoEsq].valor;
for ( int i=1; i<=contagem[0]; i++ )
soma-=arvore[arvore[tmp[0][i]].filhoEsq].valor;
if ( k<=soma )
{
for ( int i=1; i<=contagem[1]; i++ )
tmp[1][i]=arvore[tmp[1][i]].filhoEsq;
for ( int i=1; i<=contagem[0]; i++ )
tmp[0][i]=arvore[tmp[0][i]].filhoEsq;
return consultar( esq,meio,k );
}
else
{
for ( int i=1; i<=contagem[1]; i++ )
tmp[1][i]=arvore[tmp[1][i]].filhoDir;
for ( int i=1; i<=contagem[0]; i++ )
tmp[0][i]=arvore[tmp[0][i]].filhoDir;
return consultar( meio+1,dir,k-soma );
}
}
int inicializarConsulta( int esq,int dir,int k )
{
memset( tmp,0,sizeof(tmp) );
contagem[0]=contagem[1]=0;
for ( int i=dir; i; i-=baixaBit(i) )
tmp[1][++contagem[1]]=raizes[i];
for ( int i=esq-1; i; i-=baixaBit(i) )
tmp[0][++contagem[0]]=raizes[i];
return consultar( 1,tamanho,k );
}
int main()
{
scanf( "%d%d",&n,&m );
for ( int i=1; i<=n; i++ )
scanf( "%d",&valores[i] ),numeros[++tamanho]=valores[i];
for ( int i=1; i<=m; i++ )
{
scanf( "%s",operacao );
consultas[i].tipo=(operacao[0]=='Q');
if ( consultas[i].tipo ) scanf( "%d%d%d",&consultas[i].l,&consultas[i].r,&consultas[i].k );
else scanf( "%d%d",&consultas[i].pos,&consultas[i].valor ),numeros[++tamanho]=consultas[i].valor;
}
sort( numeros+1,numeros+1+tamanho ); tamanho=unique( numeros+1,numeros+1+tamanho )-numeros-1;
for ( int i=1; i<=n; i++ )
inicializarModificacao( i,1 );
for ( int i=1; i<=m; i++ )
if ( consultas[i].tipo ) printf( "%d\n",numeros[inicializarConsulta(consultas[i].l,consultas[i].r,consultas[i].k)] );
else
{
inicializarModificacao( consultas[i].pos,-1 );
valores[consultas[i].pos]=consultas[i].valor;
inicializarModificacao( consultas[i].pos,1 );
}
}
Problema do k-ésimo Menor em Caminho na Árvore
P2633 Count on a tree
Descrição
Dada uma árvore com n nós, cada nó tem um valor de peso. Existem m consultas, cada uma fornecendo u, v, k, e você precisa responder qual é o k-ésimo menor valor de peso no caminho entre os nós (u xor último) e v, onde "último" é a resposta da consulta anterior, definido inicialmente como 0, ou seja, o primeiro u é em texto claro.
Abordagem
Claramente, podemos primeiro usar diferenças na árvore para manter a soma de prefixo de cada nó até a raiz.
Ao consultar u, v, podemos obter a soma de siz[raiz,u] e siz[raiz,v]. Então, usamos siz[raiz,u] + siz[raiz,v] - siz[raiz,lca] - siz[raiz,pai[lca]], e processamos os quatro nós juntos. Cada árvore de segmento correspondente a um nó herda do pai (a raiz herda da árvore de segmento vazia número 0), e essas duas operações podem ser processadas durante a construção da árvore na dfs.
Código
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10,MAXM=2e6+10;
struct aresta
{
int para,prox;
}arestas[MAXN<<1];
int n,m,s,ultimaResposta=0,contadorTotal,contagem,cabeca[MAXN];
int pesos[MAXN],tmp[MAXN],ancestral[MAXN][35],profundidade[MAXN],raiz[MAXM]={0},
filhoEsq[MAXM]={0},filhoDir[MAXM]={0},tamanho[MAXM]={0};
void adicionar( int u,int v )
{
arestas[++contadorTotal]=(aresta){v,cabeca[u]}; cabeca[u]=contadorTotal;
}
void modificar( int &raiz,int anterior,int esq,int dir,int val )
{
if ( !raiz ) raiz=++contagem;
if ( esq==dir ) { tamanho[raiz]++; return; }
int meio=(esq+dir)>>1;
if ( meio>=val ) modificar( filhoEsq[raiz],filhoEsq[anterior],esq,meio,val ),filhoDir[raiz]=filhoDir[anterior];
else modificar( filhoDir[raiz],filhoDir[anterior],meio+1,dir,val ),filhoEsq[raiz]=filhoEsq[anterior];
tamanho[raiz]=tamanho[filhoEsq[raiz]]+tamanho[filhoDir[raiz]];
}
int consultar( int raiz1,int raiz2,int raiz3,int raiz4,int esq,int dir,int k )
{
if ( esq==dir ) return esq;
int meio=(esq+dir)>>1,tmp=tamanho[filhoEsq[raiz1]]+tamanho[filhoEsq[raiz2]]-tamanho[filhoEsq[raiz3]]-tamanho[filhoEsq[raiz4]];
if ( tmp>=k ) return consultar( filhoEsq[raiz1],filhoEsq[raiz2],filhoEsq[raiz3],filhoEsq[raiz4],esq,meio,k );
else return consultar( filhoDir[raiz1],filhoDir[raiz2],filhoDir[raiz3],filhoDir[raiz4],meio+1,dir,k-tmp );
}
void dfs( int u,int pai )
{
profundidade[u]=profundidade[pai]+1;
for ( int i=cabeca[u]; i; i=arestas[i].prox )
{
int v=arestas[i].para;
if ( v==ancestral[u][0] ) continue;
ancestral[v][0]=u; modificar( raiz[v],raiz[u],1,s,pesos[v] ); dfs( v,u );
}
}
int lca( int x,int y )
{
if ( profundidade[x]<profundidade[y] ) swap( x,y );
int del=profundidade[x]-profundidade[y];
for ( int i=0; (1<<i)<=del; i++ )
if ( (1<<i)&del ) x=ancestral[x][i];
for ( int i=20; i>=0; i-- )
if ( ancestral[x][i] != ancestral[y][i] ) x=ancestral[x][i],y=ancestral[y][i];
return x==y ? x : ancestral[x][0];
}
int main()
{
scanf( "%d%d",&n,&m );
for ( int i=1; i<=n; i++ )
scanf( "%d",&tmp[i] ),pesos[i]=tmp[i];
//----------------entrada-----------------
sort( tmp+1,tmp+1+n ); s=unique( tmp+1,tmp+1+n )-tmp;
for ( int i=1,u,v; i<n; i++ )
scanf( "%d%d",&u,&v ),adicionar( u,v ),adicionar( v,u );
for ( int i=1; i<=n; i++ )
pesos[i]=lower_bound( tmp+1,tmp+1+s,pesos[i] )-tmp;
//--------------discretização-------------------
modificar( raiz[1],raiz[0],1,s,pesos[1] ); dfs( 1,0 ); int limite=log2(n);
for ( int k=1; k<=limite; k++ )
for ( int i=1; i<=n; i++ )
ancestral[i][k]=ancestral[ancestral[i][k-1]][k-1];
//-------------preparação------------------
while ( m-- )
{
int u,v,k; scanf( "%d%d%d",&u,&v,&k );
u^=ultimaResposta;
int _lca=lca(u,v),ans=tmp[consultar(raiz[u],raiz[v],raiz[_lca],raiz[ancestral[_lca][0]],1,s,k)];
printf( "%d\n",ans ); ultimaResposta=ans;
}
}