Introduction
First, let us cite the definition from the CLJ paper:
- A “persistent data structure” keeps all historical versions of the data structure, while leveraging shared data between versions to reduce time and space costs.
This article mainly discusses two algorithmic ideas, concrete implementations, and coding techniques for persistent segment trees.
Core Ideas
-
A persistent segment tree applies ideas from functional programming: recorded data is assigned but never modified. After each insertion, a historical version is saved. Then, taking advantage of the fact that segment trees built on the same value domain have identical structure and thus can be subtracted directly, we can answer range queries.
-
We use the classic range K-th problem as an example: given a sequence of n numbers, query the K-th largest element in the interval [l, r]. Here, “K-th largest” is defined as the K-th element after sorting the interval [l, r] in ascending order.
Range K-th Without Modifications
-
Let us first consider a simplified problem: querying the K-th element over the entire range. We build a segment tree over the value domain, and each node stores the count of elements within that interval. During construction and querying, the interval boundaries are passed via recursion parameters. Then we can query in the same way as a binary search tree: if the number of elements on the left, sum >= K, recursively query the left child for the K-th; otherwise recursively query the right child for the (K - sum)-th, until returning the leaf value.
-
Now we want to answer K-th queries for an interval [l, r]. If we can obtain one segment tree that inserts elements [1, l - 1] of the original sequence, and another segment tree that inserts elements [1, r], then because the segment tree is built over the value domain and the interval length is fixed, their structure must be exactly the same. We can subtract these two segment trees directly; the result is equivalent to a segment tree built by inserting elements from [l, r]. Note that this uses the interval subtraction property, which in practice subtracts two different historical versions of the segment tree: the old tree after inserting up to element l-1, and the new tree after inserting up to element r.
-
After subtraction, we obtain a segment tree that is equivalent to a tree built by inserting only the elements in [l, r] of the original sequence, and that records the element counts in each interval. Query this segment tree in BST style to get the range K-th.
-
This approach works, but obviously we cannot rebuild a completely new segment tree from scratch on each insertion; the memory cost would be unacceptable. In fact, when inserting a new element, we do not need to create all nodes anew; instead, we only create the additional nodes. That is, starting from the root, create new nodes and copy the values from the old nodes, then apply modifications.
-
In this way, at each node we only need to modify either the left child or the right child’s information. Recursing down to a leaf ends the process. The number of modified nodes equals the tree height, i.e., at most tree height new nodes are created, and the memory cost becomes manageable.
-
Note that for root[0], i.e., the tree with zero inserted elements, its left and right child pointers are both 0. This allows us to use this single node to represent an empty tree of arbitrary structure without explicitly building the tree. This is because for this node, no matter how you recurse, it always points back to itself, and the stored element count is zero.
Range K-th With Modifications
-
When we need to support element updates, if we still save historical versions in the original way, then modifying one element will affect all subsequently built segment trees, making the time cost unacceptable.
-
If you look carefully, you will find that the segment tree represented by root[i] stores the value-domain counts after inserting elements from the first up to the i-th. That is, each time we subtract segment trees for a range query, we are subtracting two prefixes [1, l - 1] and [1, r].
-
As is well known, there is a very clever and concise way to quickly maintain prefix sums of a sequence: the Binary Indexed Tree (Fenwick tree). By introducing a Fenwick tree to quickly compute prefix sums of a sequence of segment trees, we can make a functional segment tree support point updates at the cost of an additional logn factor.
-
However, there is a fairly important detail in the concrete implementation. If we fully follow the Fenwick-tree way of maintaining prefix sums—i.e., inserting elements of the original sequence one by one and maintaining prefix sums over n empty trees—then the required space is very large, because many unnecessary nodes are created, and the build-time complexity also increases by a logn factor.
-
In fact, we can first build n segment trees for the initial sequence in the no-modification way and never modify them afterward; then for each update, maintain prefix sums on another n empty trees. Adding the two parts together yields a segment tree equivalent to inserting elements from [l, r] of the original sequence with modifications supported; we then query it.
Code Implementation
Some Techniques
-
As mentioned above, in the no-modification case, we can omit explicit tree building by using the property that an empty node can be recursively descended indefinitely.
-
In the modification-supported case, for a range query, what we pass is no longer just two historical versions of the segment tree, but all the segment trees used to compute the prefix sums. Therefore, we need a global array to record the root indices of these subtrees, and when deciding whether to recurse to the left or right child, update this array using the left-child/right-child indices of each subtree root.
-
If you need to reduce memory usage, you can read all updates first, then sort and deduplicate all distinct values that ever appear and discretize them. This allows building the segment tree over a much smaller value domain; then map each element in the original sequence and updates via binary search.
No Modifications (POJ2104/HDU2665)
#include <cstring>
#include <algorithm>
#define MAX 100010
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
const int INF = 0x3f3f3f3f;
//Record the original array, the sorted array, and the root node for each element
int nums[MAX], sorted[MAX], root[MAX];
int cnt;
struct TMD
{
int sum, L_son, R_son;
} Tree[MAX<<5];
inline int CreateNode( int _sum, int _L_son, int _R_son )
{
int idx = ++cnt;
Tree[idx].sum = _sum;
Tree[idx].L_son = _L_son;
Tree[idx].R_son = _R_son;
return idx;
}
void Insert( int & root, int pre_rt, int pos, int L, int R )
{
//Update down from the root to the leaf, creating a new chain of updated nodes; this becomes a new tree.
root = CreateNode( Tree[pre_rt].sum + 1, Tree[pre_rt].L_son, Tree[pre_rt].R_son );
if ( L == R ) return;
int M = ( L + R ) >> 1;
if ( pos <= M )
Insert( Tree[root].L_son, Tree[pre_rt].L_son, pos, L, M );
else
Insert( Tree[root].R_son, Tree[pre_rt].R_son, pos, M + 1, R );
}
int Query( int S, int E, int L, int R, int K )
{
if ( L == R ) return L;
int M = ( L + R ) >> 1;
//The sum computed below is the number of elements in the left child within the current query range.
int sum = Tree[Tree[E].L_son].sum - Tree[Tree[S].L_son].sum;
if ( K <= sum )
return Query( Tree[S].L_son, Tree[E].L_son, L, M, K );
else
return Query( Tree[S].R_son, Tree[E].R_son, M + 1, R, K - sum );
}
int main()
{
int n, m, num, pos, T;
while ( scanf("%d %d", &n, &m) != EOF )
{
cnt = 0; root[0] = 0;
for ( int i = 1; i <= n; ++i )
{
scanf("%d", &nums[i]);
sorted[i] = nums[i];
}
sort( sorted + 1, sorted + 1 + n );
num = unique( sorted + 1, sorted + n + 1 ) - ( sorted + 1 );
for ( int i = 1; i <= n; ++i )
{
//In effect, a segment tree is built for each element, and its root is stored
pos = lower_bound( sorted + 1, sorted + num + 1, nums[i] ) - sorted;
Insert( root[i], root[i - 1], pos, 1, num );
}
int l, r, k;
while ( m-- )
{
scanf("%d %d %d", &l, &r, &k);
pos = Query( root[l - 1], root[r], 1, num, k );
printf("%d\n", sorted[pos]);
}
}
}
With Modifications (ZOJ2112/BZOJ1901)
using namespace std;
const int MAX = 50010;
const int MAX_q = 10010;
const int INF = 0x3f3f3f3f;
int nums[MAX], all_val[MAX + MAX_q], root[MAX<<1], prefix_l[100], prefix_r[100];
int cnt, p[2];
struct
{
int a, b, c;
char type;
} Querys[MAX_q];
struct TMD
{
int sum, L_son, R_son;
} Tree[MAX*40];
inline int Lowbit( int x )
{
return x & (-x);
}
inline int CreateNode( int _sum, int _L_son, int _R_son )
{
int idx = ++cnt;
Tree[idx].sum = _sum;
Tree[idx].L_son = _L_son;
Tree[idx].R_son = _R_son;
return idx;
}
void Build( int & root, int pre_rt, int pos, int L, int R )
{
root = CreateNode( Tree[pre_rt].sum + 1, Tree[pre_rt].L_son, Tree[pre_rt].R_son );
if ( L == R ) return;
int M = ( L + R ) >> 1;
if ( pos <= M )
Build( Tree[root].L_son, Tree[pre_rt].L_son, pos, L, M );
else
Build( Tree[root].R_son, Tree[pre_rt].R_son, pos, M + 1, R );
}
void Insert( int & root, int pos, int L, int R, int val )
{
//If this subtree has not been built, create a new node
if ( !root )
root = CreateNode( 0, 0, 0 );
Tree[root].sum += val;
if ( L == R ) return;
int M = ( L + R ) >> 1;
if ( pos <= M )
Insert( Tree[root].L_son, pos, L, M, val );
else
Insert( Tree[root].R_son, pos, M + 1, R, val );
}
int Query( int L, int R, int K )
{
if ( L == R ) return L;
int M = ( L + R ) >> 1, sum = 0;
//Compute prefix sums
for ( int i = 0; i < p[0]; i++ )
sum += Tree[Tree[prefix_r[i]].L_son].sum;
for ( int i = 0; i < p[1]; i++ )
sum -= Tree[Tree[prefix_l[i]].L_son].sum;
if ( K <= sum ) {
//Update subtree root indices used for computing prefix sums
for ( int i = 0; i < p[0]; i++ )
prefix_r[i] = Tree[prefix_r[i]].L_son;
for ( int i = 0; i < p[1]; i++ )
prefix_l[i] = Tree[prefix_l[i]].L_son;
return Query( L, M, K );
} else {
for ( int i = 0; i < p[0]; i++ )
prefix_r[i] = Tree[prefix_r[i]].R_son;
for ( int i = 0; i < p[1]; i++ )
prefix_l[i] = Tree[prefix_l[i]].R_son;
return Query( M + 1, R, K - sum );
}
}
int main()
{
int n, m, p_val, num;
char str[5];
int T; scanf("%d", &T);
while ( T-- )
{
scanf("%d %d", &n, &m);
cnt = 0; p_val = n + 1;
for ( int i = 1; i <= n; ++i )
{
scanf("%d", &nums[i]);
all_val[i] = nums[i];
}
//Read all updates and discretize
for ( int i = 0; i < m; ++i )
{
scanf("%s %d %d", str, &Querys[i].a, &Querys[i].b);
Querys[i].type = str[0];
if ( str[0] == 'Q' ) scanf("%d", &Querys[i].c);
else all_val[p_val++] = Querys[i].b;
}
sort( all_val + 1, all_val + p_val );
num = unique( all_val + 1, all_val + p_val ) - ( all_val + 1 );
//Map the initial numeric sequence directly onto the discretized value domain
for ( int i = 1; i <= n; ++i )
nums[i] = lower_bound( all_val + 1, all_val + num + 1, nums[i] ) - all_val;
for ( int i = 1; i <= n; ++i )
Build( root[i + n], root[i - 1 + n], nums[i], 1, num );
for ( int i = 0; i < m; ++i )
if ( Querys[i].type == 'Q' ) {
p[0] = p[1] = 1;
//Initialize segment tree roots used to compute prefix sums
prefix_r[0] = root[Querys[i].b + n];
prefix_l[0] = root[Querys[i].a - 1 == 0 ? 0 : Querys[i].a - 1 + n];
for ( int arr = Querys[i].b; arr; arr -= Lowbit(arr) )
prefix_r[p[0]++] = root[arr];
for ( int arr = Querys[i].a - 1; arr; arr -= Lowbit(arr) )
prefix_l[p[1]++] = root[arr];
printf("%d\n", all_val[Query( 1, num, Querys[i].c )]);
} else {
for ( int j = Querys[i].a; j <= n; j += Lowbit(j) )
Insert( root[j], nums[Querys[i].a], 1, num, -1 );
//Map the modified result to the value domain and update prefix sums
nums[Querys[i].a] = lower_bound( all_val + 1, all_val + num + 1, Querys[i].b ) - all_val;
for ( int j = Querys[i].a; j <= n; j += Lowbit(j) )
Insert( root[j], nums[Querys[i].a], 1, num, 1 );
}
CLR( root, 0 );
}
}