The universal segment tree

Vadym Gordiichuk

2019.02.07

First of all, I want to thank lecturers Alexander Antonenko (asantonenko@gmail.com), Arthur Maximov and Igor Mazurok. I guess, if not their advices and lectures, and also excellent exposition of educational material, the universal segment tree I’ve made would either have less comfortable usage, or simply not exist.

Note: in order this article to have the maximal use for the reader, he/she must have the basic cognition of C++ programming language and certain idea of asymptotics and mathematical notations.

Notation of function \(f\) such as relation between cartesian product of sets and a certain other set, for example \(f: A \times B \to C\) means, that function \(f = f \left( x, y \right)\) takes two arguments \(x\) and \(y\), where \(x \in A\) (verbally: \(x\) from set \(A\)), \(y \in B\), and result is element of the \(C\) set, i.e. \(f \left( a, b \right) \in C\). In other words, under notations, such as \(f: A \times B \to C\) the reader may understand the following: function \(f\) defined so that for element \(a\) from set \(A\) and for element \(b\) from set \(B\) exists such an element \(c\) from set \(C\), that \(f \left( a, b \right) = c\).

Supporting materials

Definition: Suppose \(G\) – non-empty set. Binary operation \(\circ\) on this set (\(\circ: G \times G \to G\)) is called associative, if for any elements \(a\), \(b\) and \(c\) from the set \(G\) the following condition is satisfied:
\(\left( a \circ b \right)\) \(\circ\) \(c\) \(=\) \(a\) \(\circ\) \(\left( b \circ c \right)\)

\({\mathbb{N}}_0 = \mathbb{N} \cup \{ 0 \}\), where \(\mathbb{N}\) – set of natural numbers.

The task of multiple results and modifications on a segment

In programming tasks of the form below are met:
Suppose a \(G\) – given certain non-empty set of observed operands, \(\circ:\) \(G\) \(\times\) \(G\) \(\to\) \(G\) – certain associative binary operation on the set \(G\) and \(M\) – non-empty set of modifiers, \(f: G \times M \to G\) – function-modifier of elements of the set \(G\). Let in the input stream be given: numbers \(n, m \in \mathbb{N}\); array of \(n\) elements \(a_{i}\), \(a_{i} \in G\), \(i = \overline{0, n-1}\) \(\left( a_{0}, a_{1}, \ldots, a_{n-2}, a_{n-1} \right)\).
After the array follow \(m\) queries of two types:

  1. Query of result calculation: in the input stream two numbers \(l\), \(r\) are given, \(0 \le l \le r \le n-1\), \(l, r \in {\mathbb{N}}_0\). Calculate result of operation \(\circ\) on the segment \(\left[ l, r \right]\) – \(A_{\left[ l, r \right]}\), where \(A_{\left[ l, r \right]} = a_l \circ a_{l+1} \circ \ldots \circ a_{r-1} \circ a_r\), and put it into the output stream;
  2. Query of segment modification: in the input stream are given two numbers \(l\), \(r\), \(0 \le l \le r \le n-1\), \(l, r \in {\mathbb{N}}_0\) and a certain value \(y\), \(y \in M\). Modify the segment \(\left[ l, r \right]\), by replacing values of elements \(a_i\) to \(f \left( a_i, y \right)\), \(i = \overline{l, r}\).

Often tasks of such type are reduced to the solvable with usage of segment tree for the multiple modification (further – STMM). Possibly, later I’ll try to expound in detail the basic principles of its work. In the main they are based on the following two ideas:

  1. Modify not the segment, but only vertexes, which are responsible for the result of operation \(\circ\) on it.
  2. Modifications are accumulated, and are being applied on the lesser segments only then, when there are given requests for the segments, which were affected by these modifications.

I’ll explain, why exactly STMM is being used.

Often beginner programmers begin to solve tasks of such type with so called “naive method”: modifications and calculations of the given result of operation \(\circ\) are being made with a cycle, directly.
Pseudocode of such solution:

Asymptotical complexity of modification of segment at this implementation makes itin the worst cases up to \(O \left( n \cdot c_{f} \right)\), and complexity of calculation of result on the segment of operation – \(O \left( n \cdot c_{\circ} \right)\), where \(c_{f}\) – complexity of perfomance of the modification of elements of array by the function \(f\), \(c_{\circ}\) – complexity of performance of a single operation \(\circ\). The general asymptotical complexity of the program wherein will be \(O \left( m \cdot n \cdot \left(c_{f}+c_{\circ}\right) \right)\), because the task gives \(m\) queries.

Segments tree for the multiple modification allows to shorten the time consumption and noticeably improve the general asymptotics of the program up to \(O \left( \left( n + m \right) \cdot \log_{2}{n} \cdot \left( c_{f}+c_{\circ} \right) \right)\).

Unconditionally, for every task there is its own solution. However, the most of tasks contain regularities, which allow one way or another to simplify their solution. In assumption of such reasonings, I decided to realize the universal segment tree for the multiple modification, since it’s much more simpler to use the ready solution for the most of varieties of the tasks, than rewriting it for every new task from the beginning, but with little differences. It may be imperfect for solution of every task of the form, which was noticed in the beginning of this article (in addition there may exist varieties of this task, which are solvable without this tree at all), however the quickest solution of the task in the moment of its setting (what is the most often met in Olympiad programming) compensates that. In addition, in the future universal segment tree may be used as a template and be slightly modified or optimized specifically specially for the concrete task.

This way or another, I’ll give the code of universal STMM, and also additional conditions, which are being applied on the task for application of this data structure and a manual of its usage. Pay attention, that it’s not necessary (though useful) for You to know principles of STMM’s operation or to try to get the written below code completely, in order to solve task with usage of universal STMM.

The code of the universal STMM (on C++ language)

STMM: version 1.2.0 (recursive)

In this version of the tree recursion is being used. The testing has shown, that it works (approximately) 26% quicker, than the version of the tree, which uses std::stack for preventing system stack’s overload. Personally I recommend to use exactly this version, however for the tasks with excessively (which is unlikely to happen) big amount \(n\) of elements of array it may cause errors.

STMM: version 1.2.0 (stack-using)

In this version of the tree data structure std::stack is being used. Recommended to use only to prevent system stack’s overload (in the tasks with excessively big amount \(n\) of elements of array), because recursive realization of the tree works (approximately) 26% quicker, than this one.

Conditions of the STMM’s applicability

Must be defined extended set of modifiers \(M_{2}\), which satisfies condition:

  • if exists certain neutral modifier \(e_{M} \in M\), which satisfies condition \(\forall a \in G:\) \(f \left( a, e_{M} \right)\) \(=\) \(a\), then \(M_{2}\) \(=\) \(M\),
  • else must be defined an element \(e_{M}\), which is a neutral marker (i. e. formal neutral modifier) and which satisfies condition \(e_{M} \notin M\), and then \(M_{2}\) \(=\) \(M \cup \{ e_{M} \}\).

For the function-modifier \(f\):

  1. must exist combining function \(C: M_{2} \times M \to M\), which combines accumulated modifiers, and satisfies conditions:
    • condition of unification: \(\forall a \in G\), \(\forall m_{1}, m_{2} \in M\): \(f \left( a, {C \left( m_{1}, m_{2} \right)} \right)\) \(=\) \(f \left( {f \left( a, m_{1} \right)}, m_{2} \right)\);
    • condition of the neutral modifier/marker: \(\forall m \in M\): \(C \left( e_{M}, m \right)\) \(=\) \(m\)
  2. must exist distributing function \(K: M \times \mathbb{N} \to M\), which distributes modifier, applied to the whole segment of certain length, and which for the segment \(\left[ l, r \right]\), which is being modified by modifier \(m \in M\), where \(a_{l}\), \(a_{l+1}\), \(\ldots\), \(a_{r-1}\), \(a_{r}\) – modified elements of this segment, and \(\delta = r – l + 1 \ge 1\) – amount of these elements, satisfies condition:
    \(f \left( {a_{l} \circ a_{l+1} \circ \ldots \circ a_{r-1} \circ a_{r}}, {K \left( m, \delta \right)} \right)\) \(=\) \(f \left( a_{l}, m \right) \circ f \left( a_{l+1}, m \right) \circ \ldots \circ f \left( a_{r-1}, m \right) \circ f \left( a_{r}, m \right)\)
  3. according to the distributing function \(K\) must be defined an extended function-modifier \(F: G \times M \times \mathbb{N} \to G\), which modifies result on segment \(\left[ l, r \right]\) with amount of elements \(\delta = r – l + 1\):
    \(F \left( {a_{l} \circ a_{l+1} \circ \ldots \circ a_{r-1} \circ a_{r}}, m, \delta \right)\) \(=\) \(f \left( {a_{l} \circ a_{l+1} \circ \ldots \circ a_{r-1} \circ a_{r}}, {K \left( m, \delta \right)} \right)\).

    Note

    I want to note, that for the case, when only one element with the number \(i\) is modified, i.e. then, when left and right limits of modified segment are equal \(l = r = i\), and \(\delta = 1\), extended function-modifier \(F\) by its definition equals to the initial \(f\):
    \(F \left( a_{i}, m, \delta \right)\) \(=\) \(F \left( a_{i}, m, 1 \right)\) \(=\) \(f \left( a_i, m \right)\). This makes STMM applicable even for the tasks, in which not the segments, but separate elements of the array are modified (so called tasks of single modifications).

Documentation of the universal STMM

Manual of usage

  1. Copy the code of universal STMM into the program, where its usage is planned, or include it from an independent library.
  2. Define the data structures with public constructors without arguments, which satisfy the role of observed operands from the set \(G\) and the role of modifiers from the set \(M_{2}\):

    Note: depending on the task, the used data structures/types may be already defined. For example, the role of observed elements and modifiers may be played by the standard data type int. That’s why this item of the list may be unnecessary, depending on the task.

  3. Describe the given on the set \(G\) operation \(\circ\), extended modifier-function \(F\) and combining function \(C\):

  4. Define object of “segment tree” type, by giving it as parameters for the template types of operands and modifiers:

  5. Construct the segment tree with one of methods:
    • method read:
      Describe the function-preprocessor (which, for example, reads the data directly from the input stream, processes them and using them builds elements of array from the statement), which will create elements of the array from the task one-by-one from the element with number \(0\) and to the element with number \(n-1\).

      With function-preprocessor and known amount of the elements \(n\) build the segment tree, with calling method read, by giving it as an arguments respectively amount of elements \(n\), function-preprocessor, operation \(\circ\), extended function-modifier \(F\), combining function \(C\) and neutral modifier/marker \(e_{M}\):

    • method construct:
      Define certain non-empty array of elements \(G\) with address of the beginning begin and address of the end end (i. e. all the elements \(a_{i}\) must be in the interval \(\left[ {begin}, {end} \right)\), and if array has length \(n\), then end \(=\) begin+n)
      Build the segment tree, by calling method construct, giving it as an arguments respectively address of the beginning of the array, address of the end of the array, operation \(\circ\), extended modifier-function \(F\), combine function \(C\) and neutral modifier/marker \(e_{M}\):

      First the data structure will copy the initial array, and then basing it builds the segment tree. This method is useful, when there is a need to save the initial array, and use it in the future.

  6. Perform the query of result and modification according to the following:
    1. Define left and right limits of the observed segment:

    2. Define the type of query to the segment tree, and call the method of the tree the corresponding to this query:
      1. for the requests of segment modification:
        define certain modifier m:

        and call the segment tree’s method modify, with giving it as an arguments left limit of modified segment, right limit of modified segment and modifier m:

      2. for queries of the result of operation \(\circ\) on a segment call method result, by giving it as an arguments the left and the right limits of modified segment:

Methods of class

Denotations:

  • \(n\) – amount of elements in the initial array.
  • \(m_{G}\) – amount of memory, taken by the element of set \(G\)
  • \(m_{M}\) – amount of memory, taken by the modifier from set \(M_{2}\)
  • \(c_{F}\) – complexity of modification of element of set \(G\) with extended modifier-function \(F\).
  • \(c_{C}\) – complexity of combining function \(C\).
  • \(c_{\circ}\) – complexity of perfomance of a single operation \(\circ\).
  • TYPE – type of operands of set \(G\).
  • MODIFIER_TYPE – type of modifiers from set \(M_{2}\).
Name of method Description of method
construct Type of returned value: void

Arguments
  1. const TYPE *begin – adress of the beginning of copied array;
  2. const TYPE *end – adress of the end of copied array;
  3. TYPE f(const TYPE&, const TYPE&) – operation \(\circ\) of the set \(G\);
  4. TYPE modifier_function(const TYPE&, const MODIFIER_TYPE&, const size_t&) – extended modifier-function \(F\);
  5. MODIFIER_TYPE modification_combine(const MODIFIER_TYPE&, const MODIFIER_TYPE&) – combining function \(C\);
  6. const MODIFIER_TYPE& new_neutral_modifier – neutral modifier/marker \(e_{M}\).

Time usage: \(O \left( {c_{\circ}} \cdot n \right)\); \(2 \cdot n + {\log_{2}{n}} + n \cdot {c_{\circ}}\) in the worst case, \(2 \cdot n + n \cdot c_{\circ}\) in the best.
Memory usage: \(O \left( n \cdot \left( m_{G} + m_{M} \right) \right)\); \({\log_{2}{n}} + 2 \cdot n \cdot m_{G} + n \cdot m_{M}\) in the worst case, \(2 \cdot n \cdot m_{G} + n \cdot m_{M}\) in the best.
Description: builds the segment tree, basing on the given array with copying its elements directly into the tree.

read Type of returned value: void

Arguments
  1. const size_t& amount_of_elements – amount of elements from the set \(G\);
  2. TYPE preprocessing_function() – function-preprocessor, which creates observed elements of the tree;
  3. TYPE f(const TYPE&, const TYPE&) – operation \(\circ\) of the set \(G\);
  4. TYPE modifier_function(const TYPE&, const MODIFIER_TYPE&, const size_t&) – extended modifier-function \(F\);
  5. MODIFIER_TYPE modification_combine(const MODIFIER_TYPE&, const MODIFIER_TYPE&) – combining function \(C\);
  6. const MODIFIER_TYPE& new_neutral_modifier – neutral modifier/marker \(e_{M}\).

Time usage: \(O \left( {c_{\circ}} \cdot n \right)\); \(2 \cdot n + {\log_{2}{n}} + n \cdot {c_{\circ}}\) in the worst case, \(2 \cdot n + n \cdot c_{\circ}\) in the best.
Memory usage: \(O \left( n \cdot \left( m_{G} + m_{M} \right) \right)\); \({\log_{2}{n}} + 2 \cdot n \cdot m_{G} + n \cdot m_{M}\) in the worst case, \(2 \cdot n \cdot m_{G} + n \cdot m_{M}\) in the best.
Description: builds the tree basing on the given function-preprocessor, with calling it \(n\) times and writing the returned by it elements of set \(G\) one by one.

modify Type of returned value: void

Arguments
  1. const size_t& i – index of modified element;
  2. const MODIFIER_TYPE& modifier – modifier from the set \(M\).

Time usage: \(O \left( \left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n} \right)\); \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot 2 \cdot \log_{2}{n}\) in the worst case, \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n}\) in the best.
Memory usage: \(O \left( \left( m_{G} + m_{M} \right) \cdot \log_{2}{n} \right)\); \(\left( m_{G} + m_{M} \right) \cdot 2 \cdot \log_{2}{n}\) in the worst case, \(\left( m_{G} + m_{M} \right) \cdot \log_{2}{n}\) in the best.
Description: modifies element with given index by using given modifier.

modify Type of returned value: void

Arguments
  1. const size_t& l – index of left limit of modified segment;
  2. const size_t& r – index of right limit of modified segment;
  3. const MODIFIER_TYPE& modifier – modifier from the set \(M\).

Time usage: \(O \left( \left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n} \right)\); \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot 2 \cdot \log_{2}{n}\) in the worst case, \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n}\) in the best.
Memory usage: \(O \left( \left( m_{G} + m_{M} \right) \cdot \log_{2}{n} \right)\); \(\left( m_{G} + m_{M} \right) \cdot 2 \cdot \log_{2}{n}\) in the worst case, \(\left( m_{G} + m_{M} \right) \cdot \log_{2}{n}\) in the best.
Description: modifies segment with given limits by using given modifier.

result Type of returned value: TYPE

Arguments
  1. const size_t& l – index of left limit of segment;
  2. const size_t& r – – index of right limit of segment;

Time usage: \(O \left( \left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n} \right)\); \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot 2 \cdot \log_{2}{n}\) in the worst case, \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n}\) in the best.
Memory usage: \(O \left( \left( m_{G} + m_{M} \right) \cdot \log_{2}{n} \right)\); \(\left( m_{G} + m_{M} \right) \cdot 2 \cdot \log_{2}{n}\) in the worst case, \(\left( m_{G} + m_{M} \right) \cdot \log_{2}{n}\) in the best.
Description: returns result of operation \(\circ\) on the given segment.