#include <routing_filters.h>

Public Member Functions
	WeightedWaveletTree ()=default

void	Clear ()

int	TreeSize () const
	Returns the total number of elements in trees.

void	PushBack (int64_t height, int64_t weight)
	Adds an element at index this->Size().

void	MakeTreeFromNewElements ()

int64_t	RangeSumWithThreshold (int64_t threshold_height, int begin_index, int end_index) const

Detailed Description

This class allows making fast range queries on sequences of elements.

Main characteristics.
queries on sequences of elements {height, weight}, parametrized by (begin, end, T), returning sum_{i \in [begin, end), S[i].height >= T} S[i].weight
O(log (#different heights)) time complexity thanks to an underlying wavelet tree (https://en.wikipedia.org/wiki/Wavelet_Tree)
holds several sequences at once, can be cleared while still keeping allocated memory to avoid allocations. More details on these points follow.
Query complexity. The time complexity of a query in S is O(log H), where H is the number of different heights appearing in S. The particular implementation guarantees that queries that are trivial in the .height dimension, that is if threshold_height is <= or >= all heights in the range, are O(1).
Initialization complexity. The time complexity of filling the underlying data structures, which is done by running MakeTreeFromNewElements(), is O(N log N) where N is the number of new elements. The space complexity is a O(N log H).
Usage. Given Histogram holding elements with fields {.height, .weight}, Histogram hist1 {{2, 3}, {1, 4}, {4, 1}, {2, 2}, {3, 1}, {0, 4}}; Histogram hist2 {{-2, -3}, {-1, -4}, {-4, -1}, {-2, -2}}; WeightedWaveletTree tree;

for (const auto [height, weight] : hist1]) { tree.PushBack(height, weight); } const int begin1 = tree.TreeSize(); tree.MakeTreeFromNewElements(); const int end1 = tree.TreeSize(); const int begin2 = tree.TreeSize(); ///< begin2 == end1. for (const auto [height, weight] : hist2]) { tree.PushBack(height, weight); } tree.MakeTreeFromNewElements(); const int end2 = tree.TreeSize();

///< Sum of weights on whole first sequence, == 3 + 4 + 1 + 2 + 1 + 4 tree.RangeSumWithThreshold(/*threshold=*‍/0, /*begin=*‍/begin1, /*end=*‍/end1); ///< Sum of weights on whole second sequence, all heights are negative, ///< so the result is 0. tree.RangeSumWithThreshold(/*threshold=*‍/0, /*begin=*‍/begin2, /*end=*‍/end2); ///< This is forbidden, because the range overlaps two sequences. tree.RangeSumWithThreshold(/*threshold=*‍/0, /*begin=*‍/2, /*end=*‍/10); ///< Returns 2 = 0 + 1 + 0 + 1. tree.RangeSumWithThreshold(/*threshold=*‍/3, /*begin=*‍/1, /*end=*‍/5); ///< Returns -6 = -4 + 0 + -2. tree.RangeSumWithThreshold(/*threshold=*‍/-2, /*begin=*‍/1, /*end=*‍/4); ///< Add another sequence. Histogram hist3 {{1, 1}, {3, 4}}; const int begin3 = tree.TreeSize(); for (const auto [height, weight] : hist3) { tree.PushBack(height, weight); } tree.MakeTreeFromNewElements(); const int end3 = tree.TreeSize(); ///< Returns 4 = 0 + 4. tree.RangeSumWithThreshold(/*threshold=*‍/2, /*begin=*‍/begin3, /*end=*‍/end3); ///< Clear the tree, this invalidates all range queries. tree.Clear(); ///< Forbidden! tree.RangeSumWithThreshold(/*threshold=*‍/2, /*begin=*‍/begin3, /*end=*‍/end3);

Implementation. This data structure uses two main techniques of the wavelet tree:
a binary search tree in the height dimension.
nodes only hold information about elements in their height range, keeping selected elements in the same order as the full sequence, and can map the index of its elements to their left and right child. The layout of the tree is packed by separating the tree navigation information from the (prefix sum + mapping) information. Here is how the tree for heights 6 4 1 3 6 1 7 4 2 is laid out in memory: tree_layers_ ///< nodes_ 6 4 1 3 6 1 7 4 2 ///< 4 1 3 1 2|6 4 6 7 4 ///< 2 6 1 1|3 2|4 4|6 6 7 ///< _ 3 _ 7 _ 23| _|6 6|7 ///< Dummy information is used to pad holes in nodes_. In addition to the mapping information of each element, each node holds the prefix sum of weights up to each element, to be able to compute the sum of S[i].weight of elements in its height range, for any range, in O(1). The data structure does not actually need height information inside the tree nodes, and does not store them.

Definition at line 709 of file routing_filters.h.

Constructor & Destructor Documentation

◆ WeightedWaveletTree()

operations_research::WeightedWaveletTree::WeightedWaveletTree ( )

default

Member Function Documentation

◆ Clear()

void operations_research::WeightedWaveletTree::Clear ( )

Clears all trees, which invalidates all further range queries on currently existing trees. This does not release memory held by this object.

Definition at line 4278 of file routing_filters.cc.

◆ MakeTreeFromNewElements()

void operations_research::WeightedWaveletTree::MakeTreeFromNewElements ( )

Generates the wavelet tree for all new elements, i.e. elements that were added with PushBack() since the latest of these events: construction of this object, a previous call to MakeTreeFromNewElements(), or a call to Clear(). The range of new elements [begin, end), with begin the Size() at the latest event, and end the current Size().

New elements are elements_[i] for i in [begin_index, end_index).

Gather all heights, sort and unique them, this makes up the list of pivot heights of the underlying tree, with an inorder traversal.

Todo: (user): investigate whether balancing the tree using the number of occurrences of each height would be beneficial.

Todo

Todo: (user): use a heap-like encoding for the binary search tree: children of i at 2*i and 2*i+1. Better cache line utilization.

Remember location of the tree representation for this range of elements. tree_location_ may be smaller than elements_, extend it if needed.

Add and extend layers if needed. The amount of layers needed is 1 + ceil(log(sequence size)).

Fill all relevant locations of the tree, and record tree navigation information. This recursive function has at most num_layers call depth.

Precompute prefix sums of range [range_begin, range_end).

Range has more than one height, partition it. Record layer l -> l+1 sequence index mapping:

if height < pivot, record where this element will be in layer l+1.
if height >= pivot, record where next <= pivot will be in layer l+1.

Todo: (user): stable_partition allocates memory, find a way to fill layers without this.

Definition at line 4285 of file routing_filters.cc.

◆ PushBack()

void operations_research::WeightedWaveletTree::PushBack	(	int64_t	height,
		int64_t	weight )

inline

Adds an element at index this->Size().

Definition at line 721 of file routing_filters.h.

◆ RangeSumWithThreshold()

int64_t operations_research::WeightedWaveletTree::RangeSumWithThreshold	(	int64_t	threshold_height,
		int	begin_index,
		int	end_index ) const

Returns sum_{begin_index <= i < end_index, S[i].height >= threshold_height} S[i].weight. The range [begin_index, end_index) can only cover elements that were new at the same call to MakeTreeFromNewElements(). When calling this method, there must be no pending new elements, i.e. the last method called must not have been PushBack() or TreeSize().

Answer in O(1) for the common case where max(heights) < threshold.

Query or subquery threshold covers all elements of this node. This allows to be O(1) when the query's threshold is <= min(heights).

This node is a leaf, its height is < threshold, stop descent here.

All elements of the right child have their height above the threshold, we can project the range to the right child and add the whole subrange.

Go to the left child.

Go to the right child.

Definition at line 4364 of file routing_filters.cc.

◆ TreeSize()

int operations_research::WeightedWaveletTree::TreeSize ( ) const