Persistent range tree

persist.cpp

/*

	Implementation of a (relatively) simple persistent range tree.
	Supports point updates (set) and range-query of sums.

	Note that all the ranges in this code are [inclusive, exclusive)

	Compiles with
		g++ persist.cpp -o persist -std=c++11 -Wall -Wextra -Wshadow -Wpedantic -O2

	If this implementation is too slow or takes up too much memory, one way to speed it
	up would be to allocate a large array of nodes, because it's quicker to allocate one
	large chunk of memory at once. Instead of using pointers you can use array indexes.
	Pointers take up 8 bytes and ints only take up 4.

*/

#include <iostream>
#include <cstdlib>

// A node's default value. Usually the 'identity' value of the operator you're using.
// The tree computes sumes, so in this case it's zero.
// If your tree computed minimums, then this would be set to infinity (a large value).
const int DEFAULT_VALUE = 0;

// The number of levels in the tree. Having K levels gives (2^K) leaves.
const int TREE_LEVELS = 4;

// The 'size' of the tree. This is the number of leaves. The maximum number of nodes in a single
// tree is (TREE_SIZE * 2 - 1), but the total number of nodes overall is much larger because
// we keep every past copy of every tree.
const int TREE_SIZE = 1 << TREE_LEVELS >> 1;

struct Node {
	int value;    // The sum of all the decendant nodes, or a single value if a leaf
	Node * left;  // The left child. Might be null if node is a leaf or the node doesn't exist yet.
	Node * right; // Right child. Same stuff applies
};

// Create a copy of a node, or a create a new node if it doesn't exist
Node * copy(Node * source) {
	Node * c = new Node;
	if (source == nullptr) {
		// Apply default values
		c -> value = DEFAULT_VALUE;
		c -> left = nullptr;
		c -> right = nullptr;
	} else {
		// Copy values from existing node
		c -> value = source -> value;
		c -> left = source -> left;
		c -> right = source -> right;
	}
	return c;
}

// Get the value of a node. If it doesn't exist, return the default value instead.
int getValue(Node * node) {
	if (node == nullptr) {
		return DEFAULT_VALUE;
	}
	return node -> value;
}

// Create an updated copy of a node and its decendants. If the node doesn't actually need to be
// updated then this function will just return the node itself. Note that we pass the left and
// right points of the node to this function. If we stored these values in every node we'd run
// out of memory very quickly.
Node * update(Node * node, int index, int value, int node_left, int node_right) {
	// Check if the node we want to update is in the range
	if (node_left <= index && index < node_right) {
		if (node_left + 1 == node_right) {
			// This node is a leaf, create a copy and set the value
			node = copy(node);
			node -> value = value;
		} else {
			// This is not a leaf. Create a copy.
			node = copy(node);
			// Update the children and assign my pointers to the updated versions
			int middle = (node_left + node_right) / 2;
			node -> left = update(node -> left, index, value, node_left, middle);
			node -> right = update(node -> right, index, value, middle, node_right);
			// Update the value of this node
			node -> value = getValue(node -> left) + getValue(node -> right);
		}
	}
	// Return the node. If the node wasn't modified, then this will be unchanged.
	// If a new version was created it will return that.
	return node;
}

// Query a range on the tree
int query(Node * node, int query_left, int query_right, int node_left, int node_right) {
	// If the node doesn't exist, can't do anything with it
	if (node != nullptr) {
		// Check if the query range overlaps the range of the node
		if (query_left < node_right && query_right > node_left) {
			if (query_left <= node_left && node_right <= query_right) {
				// If the query range completely covers the node, return this node's value
				// (which is the sum of this range)
				return node -> value;
			} else {
				// Partial overlap, query the children and get the sum
				int middle = (node_left + node_right) / 2;
				return query(node -> left,  query_left, query_right, node_left, middle)
				     + query(node -> right, query_left, query_right, middle, node_right);
			}
		}
	}
	// We'll end up here if the node doesn't exist or doesn't overlap the range
	return DEFAULT_VALUE;
}

// Display the tree
void printTree(Node * node, int indent) {
	if (indent < TREE_LEVELS) {
		if (node == nullptr) {
			for (int i = 0; i < indent; ++i) std::cout << "    ";
			std::cout << "*\n";
		} else {
			printTree(node -> left, indent + 1);
			for (int i = 0; i < indent; ++i) std::cout << "    ";
			std::cout << node -> value << '\n';
			printTree(node -> right, indent + 1);
		}
	}
}

int main() {
	// Generate a tree, printing it out after every update
	Node * root = copy(nullptr);
	for (int i = 0; i < TREE_SIZE; ++i) {
		root = update(root, i, rand() % 10, 0, TREE_SIZE);
		printTree(root, 0);
		std::cout << "--------------------\n";
	}
	// Make some random range queries.
	for (int i = 0; i < TREE_SIZE; ++i) {
		int right = 1 + (rand() % (TREE_SIZE - 1));
		int left = rand() % right;
		std::cout << left << ' ' << right << " : " << query(root, left, right, 0, TREE_SIZE) << '\n';
	}
}