Prerequisite : Segment Tree Persistency in Data Structure
Segment Tree es en sí mismo una gran estructura de datos que entra en juego en muchos casos. En este post introduciremos el concepto de Persistencia en esta estructura de datos. Persistencia, simplemente significa retener los cambios. Pero, obviamente, retener los cambios provoca un consumo adicional de memoria y, por lo tanto, afecta la complejidad del tiempo.
Nuestro objetivo es aplicar persistencia en el árbol de segmentos y también asegurarnos de que no tome más de O(log n) tiempo y espacio para cada cambio.
C++
// C++ program to implement persistent segment
// tree.
#include "bits/stdc++.h"
using namespace std;
#define MAXN 100
/* data type for individual
* node in the segment tree */
struct node
{
// stores sum of the elements in node
int val;
// pointer to left and right children
node* left, *right;
// required constructors........
node() {}
node(node* l, node* r, int v)
{
left = l;
right = r;
val = v;
}
};
// input array
int arr[MAXN];
// root pointers for all versions
node* version[MAXN];
// Constructs Version-0
// Time Complexity : O(nlogn)
void build(node* n,int low,int high)
{
if (low==high)
{
n->val = arr[low];
return;
}
int mid = (low+high) / 2;
n->left = new node(NULL, NULL, 0);
n->right = new node(NULL, NULL, 0);
build(n->left, low, mid);
build(n->right, mid+1, high);
n->val = n->left->val + n->right->val;
}
/**
* Upgrades to new Version
* @param prev : points to node of previous version
* @param cur : points to node of current version
* Time Complexity : O(logn)
* Space Complexity : O(logn) */
void upgrade(node* prev, node* cur, int low, int high,
int idx, int value)
{
if (idx > high or idx < low or low > high)
return;
if (low == high)
{
// modification in new version
cur->val = value;
return;
}
int mid = (low+high) / 2;
if (idx <= mid)
{
// link to right child of previous version
cur->right = prev->right;
// create new node in current version
cur->left = new node(NULL, NULL, 0);
upgrade(prev->left,cur->left, low, mid, idx, value);
}
else
{
// link to left child of previous version
cur->left = prev->left;
// create new node for current version
cur->right = new node(NULL, NULL, 0);
upgrade(prev->right, cur->right, mid+1, high, idx, value);
}
// calculating data for current version
// by combining previous version and current
// modification
cur->val = cur->left->val + cur->right->val;
}
int query(node* n, int low, int high, int l, int r)
{
if (l > high or r < low or low > high)
return 0;
if (l <= low and high <= r)
return n->val;
int mid = (low+high) / 2;
int p1 = query(n->left,low,mid,l,r);
int p2 = query(n->right,mid+1,high,l,r);
return p1+p2;
}
int main(int argc, char const *argv[])
{
int A[] = {1,2,3,4,5};
int n = sizeof(A)/sizeof(int);
for (int i=0; i<n; i++)
arr[i] = A[i];
// creating Version-0
node* root = new node(NULL, NULL, 0);
build(root, 0, n-1);
// storing root node for version-0
version[0] = root;
// upgrading to version-1
version[1] = new node(NULL, NULL, 0);
upgrade(version[0], version[1], 0, n-1, 4, 1);
// upgrading to version-2
version[2] = new node(NULL, NULL, 0);
upgrade(version[1],version[2], 0, n-1, 2, 10);
cout << "In version 1 , query(0,4) : ";
cout << query(version[1], 0, n-1, 0, 4) << endl;
cout << "In version 2 , query(3,4) : ";
cout << query(version[2], 0, n-1, 3, 4) << endl;
cout << "In version 0 , query(0,3) : ";
cout << query(version[0], 0, n-1, 0, 3) << endl;
return 0;
}
Java
// Java program to implement persistent
// segment tree.
class GFG{
// Declaring maximum number
static Integer MAXN = 100;
// Making Node for tree
static class node
{
// Stores sum of the elements in node
int val;
// Reference to left and right children
node left, right;
// Required constructors..
node() {}
// Node constructor for l,r,v
node(node l, node r, int v)
{
left = l;
right = r;
val = v;
}
}
// Input array
static int[] arr = new int[MAXN];
// Root pointers for all versions
static node version[] = new node[MAXN];
// Constructs Version-0
// Time Complexity : O(nlogn)
static void build(node n, int low, int high)
{
if (low == high)
{
n.val = arr[low];
return;
}
int mid = (low + high) / 2;
n.left = new node(null, null, 0);
n.right = new node(null, null, 0);
build(n.left, low, mid);
build(n.right, mid + 1, high);
n.val = n.left.val + n.right.val;
}
/* Upgrades to new Version
* @param prev : points to node of previous version
* @param cur : points to node of current version
* Time Complexity : O(logn)
* Space Complexity : O(logn) */
static void upgrade(node prev, node cur, int low,
int high, int idx, int value)
{
if (idx > high || idx < low || low > high)
return;
if (low == high)
{
// Modification in new version
cur.val = value;
return;
}
int mid = (low + high) / 2;
if (idx <= mid)
{
// Link to right child of previous version
cur.right = prev.right;
// Create new node in current version
cur.left = new node(null, null, 0);
upgrade(prev.left, cur.left, low,
mid, idx, value);
}
else
{
// Link to left child of previous version
cur.left = prev.left;
// Create new node for current version
cur.right = new node(null, null, 0);
upgrade(prev.right, cur.right, mid + 1,
high, idx, value);
}
// Calculating data for current version
// by combining previous version and current
// modification
cur.val = cur.left.val + cur.right.val;
}
static int query(node n, int low, int high,
int l, int r)
{
if (l > high || r < low || low > high)
return 0;
if (l <= low && high <= r)
return n.val;
int mid = (low + high) / 2;
int p1 = query(n.left, low, mid, l, r);
int p2 = query(n.right, mid + 1, high, l, r);
return p1 + p2;
}
// Driver code
public static void main(String[] args)
{
int A[] = { 1, 2, 3, 4, 5 };
int n = A.length;
for(int i = 0; i < n; i++)
arr[i] = A[i];
// Creating Version-0
node root = new node(null, null, 0);
build(root, 0, n - 1);
// Storing root node for version-0
version[0] = root;
// Upgrading to version-1
version[1] = new node(null, null, 0);
upgrade(version[0], version[1], 0, n - 1, 4, 1);
// Upgrading to version-2
version[2] = new node(null, null, 0);
upgrade(version[1], version[2], 0, n - 1, 2, 10);
// For print
System.out.print("In version 1 , query(0,4) : ");
System.out.print(query(version[1], 0, n - 1, 0, 4));
System.out.print("\nIn version 2 , query(3,4) : ");
System.out.print(query(version[2], 0, n - 1, 3, 4));
System.out.print("\nIn version 0 , query(0,3) : ");
System.out.print(query(version[0], 0, n - 1, 0, 3));
}
}
// This code is contributed by mark_85
C#
// C# program to implement persistent
// segment tree.
using System;
class node
{
// Stores sum of the elements in node
public int val;
// Reference to left and right children
public node left, right;
// Required constructors..
public node()
{}
// Node constructor for l,r,v
public node(node l, node r, int v)
{
left = l;
right = r;
val = v;
}
}
class GFG{
// Declaring maximum number
static int MAXN = 100;
// Making Node for tree
// Input array
static int[] arr = new int[MAXN];
// Root pointers for all versions
static node[] version = new node[MAXN];
// Constructs Version-0
// Time Complexity : O(nlogn)
static void build(node n, int low, int high)
{
if (low == high)
{
n.val = arr[low];
return;
}
int mid = (low + high) / 2;
n.left = new node(null, null, 0);
n.right = new node(null, null, 0);
build(n.left, low, mid);
build(n.right, mid + 1, high);
n.val = n.left.val + n.right.val;
}
/* Upgrades to new Version
* @param prev : points to node of previous version
* @param cur : points to node of current version
* Time Complexity : O(logn)
* Space Complexity : O(logn) */
static void upgrade(node prev, node cur, int low,
int high, int idx, int value)
{
if (idx > high || idx < low || low > high)
return;
if (low == high)
{
// Modification in new version
cur.val = value;
return;
}
int mid = (low + high) / 2;
if (idx <= mid)
{
// Link to right child of previous version
cur.right = prev.right;
// Create new node in current version
cur.left = new node(null, null, 0);
upgrade(prev.left, cur.left, low,
mid, idx, value);
}
else
{
// Link to left child of previous version
cur.left = prev.left;
// Create new node for current version
cur.right = new node(null, null, 0);
upgrade(prev.right, cur.right,
mid + 1, high, idx, value);
}
// Calculating data for current version
// by combining previous version and current
// modification
cur.val = cur.left.val + cur.right.val;
}
static int query(node n, int low, int high,
int l, int r)
{
if (l > high || r < low || low > high)
return 0;
if (l <= low && high <= r)
return n.val;
int mid = (low + high) / 2;
int p1 = query(n.left, low, mid, l, r);
int p2 = query(n.right, mid + 1, high, l, r);
return p1 + p2;
}
// Driver code
public static void Main(String[] args)
{
int[] A = { 1, 2, 3, 4, 5 };
int n = A.Length;
for(int i = 0; i < n; i++)
arr[i] = A[i];
// Creating Version-0
node root = new node(null, null, 0);
build(root, 0, n - 1);
// Storing root node for version-0
version[0] = root;
// Upgrading to version-1
version[1] = new node(null, null, 0);
upgrade(version[0], version[1], 0,
n - 1, 4, 1);
// Upgrading to version-2
version[2] = new node(null, null, 0);
upgrade(version[1], version[2], 0,
n - 1, 2, 10);
// For print
Console.Write("In version 1 , query(0,4) : ");
Console.Write(query(version[1], 0, n - 1, 0, 4));
Console.Write("\nIn version 2 , query(3,4) : ");
Console.Write(query(version[2], 0, n - 1, 3, 4));
Console.Write("\nIn version 0 , query(0,3) : ");
Console.Write(query(version[0], 0, n - 1, 0, 3));
}
}
// This code is contributed by sanjeev2552
Javascript
<script>
// JavaScript program to implement persistent
// segment tree.
class node
{
// Node constructor for l,r,v
constructor(l, r, v)
{
this.left = l;
this.right = r;
this.val = v;
}
}
// Declaring maximum number
var MAXN = 100;
// Making Node for tree
// Input array
var arr = Array(MAXN);
// Root pointers for all versions
var version = Array(MAXN);
// Constructs Version-0
// Time Complexity : O(nlogn)
function build(n, low, high)
{
if (low == high)
{
n.val = arr[low];
return;
}
var mid = parseInt((low + high) / 2);
n.left = new node(null, null, 0);
n.right = new node(null, null, 0);
build(n.left, low, mid);
build(n.right, mid + 1, high);
n.val = n.left.val + n.right.val;
}
/* Upgrades to new Version
* @param prev : points to node of previous version
* @param cur : points to node of current version
* Time Complexity : O(logn)
* Space Complexity : O(logn) */
function upgrade(prev, cur, low, high, idx, value)
{
if (idx > high || idx < low || low > high)
return;
if (low == high)
{
// Modification in new version
cur.val = value;
return;
}
var mid = parseInt((low + high) / 2);
if (idx <= mid)
{
// Link to right child of previous version
cur.right = prev.right;
// Create new node in current version
cur.left = new node(null, null, 0);
upgrade(prev.left, cur.left, low,
mid, idx, value);
}
else
{
// Link to left child of previous version
cur.left = prev.left;
// Create new node for current version
cur.right = new node(null, null, 0);
upgrade(prev.right, cur.right,
mid + 1, high, idx, value);
}
// Calculating data for current version
// by combining previous version and current
// modification
cur.val = cur.left.val + cur.right.val;
}
function query(n, low, high, l, r)
{
if (l > high || r < low || low > high)
return 0;
if (l <= low && high <= r)
return n.val;
var mid = parseInt((low + high) / 2);
var p1 = query(n.left, low, mid, l, r);
var p2 = query(n.right, mid + 1, high, l, r);
return p1 + p2;
}
// Driver code
var A = [1, 2, 3, 4, 5];
var n = A.length;
for(var i = 0; i < n; i++)
arr[i] = A[i];
// Creating Version-0
var root = new node(null, null, 0);
build(root, 0, n - 1);
// Storing root node for version-0
version[0] = root;
// Upgrading to version-1
version[1] = new node(null, null, 0);
upgrade(version[0], version[1], 0,
n - 1, 4, 1);
// Upgrading to version-2
version[2] = new node(null, null, 0);
upgrade(version[1], version[2], 0,
n - 1, 2, 10);
// For print
document.write("In version 1 , query(0,4) : ");
document.write(query(version[1], 0, n - 1, 0, 4));
document.write("<br>In version 2 , query(3,4) : ");
document.write(query(version[2], 0, n - 1, 3, 4));
document.write("<br>In version 0 , query(0,3) : ");
document.write(query(version[0], 0, n - 1, 0, 3));
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA