Universal segment tree. Example

Vadym Gordiichuk

This article, in fact, is an addition to the article about universal segment tree (which will be further referred as the Base Article). Here will be given an example, how to use unversal segment tree for the tasks of multiple modification.

So, let’s take the following task as an example for solution:

task #2939 of site www.e-olymp.com

Dima and array

Mother gave Dima as a present an array of length \(n\). The array is not simple, but special. Dima can choose three numbers \(i\), \(j\) and \(d\) (\(1 \le i \le j \le n\), \(-1000 \le d \le 1000\)), and all elements with indexes from \(i\) to \(j\) magically become equal to \(d\). Dima plays with his array, and mother gives his questions time from time – what is the sum of all the numbers in array with indexes from \(f\) to \(t\)? Dima easily managed this problem, but what about you?

Input

The first line contains two integers \(n\) and \(q\) (\(1 \le n \le 5 \cdot 10^5\), \(1 \le q \le 10^5\)) – the number of elements in array and the total number of operations. In the next line \(n\) numbers are given: \(a_1\), \(a_2\), \(\ldots\), \(a_n\) (\(-1000 \le a_i \le 1000\)) – the initial state of array. The next \(q\) lines contain the operations and queries. The first character in the line can be either = or ?. If the line starts with =, this is an assignment operation. Next values are \(i\), \(j\) and \(d\), their restrictions are given earlier. If the line starts with ?, this is a query. Then go numbers \(f\) and \(t\) (\(1 \le f, t \le n\)).

Output

For each query print on a separate line the sum of the numbers in array with indexes from \(f\) to \(t\) inclusive.

First of all, I want to note, that Dima is very quick boy! According to this statement, he can work even with array, which contains 500000 elements! It’s more likely that Dima is a robot with a pretty quick processor, because simple human (even enough quick to perform = and ? queries) is not able to store such an array even on paper, and even more in a head. Though, array, which was gifted to Dima by mother is magical, and “magic” is pretty acceptable explanation in science. 😀
Of course, it was joke, left for us by the authors of the task. And now let’s proceed to solution.

Solution of the task

1. Revealing of the formal model

First let’s build purely mathematical model, and then correct it for the writing of code with maximal corresponding to it.

First, what we’ll have to do is to adapt the task to the general template of tasks from the Base Article:

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}\).

First what we are going to notice is the difference between the solvable task and template: in the solvable task elements of array are numbered not from \(0\) to \(n-1\), but from \(1\) to \(n\), however this difference does not affect the main mathematical model.

So, as seen from the statement of the task, it’s possible to pick out elements of template:

  1. The set \(G\): in the given task, the role of the set \(G\) can be played by the set of integers \(\mathbb{Z}\), becayse arrat from the statement contains integers \(-1000 \le a_i \le 1000\), \(i = \overline{0, n-1}\).
  2. Associative operation \(\circ\) in set \(G\): role of this operation is played by addition \(+\), because in the task we must calculate sums on segments.
  3. Set of modifiers \(M\) and the function-modifier \(f\): according to the statement of the task, on the elements of array operation of replacement is performed: “Dima can choose three numbers \(i\), \(j\) and \(d\) (\(1 \le i \le j \le n\), \(-1000 \le d \le 1000\)), and all elements with indexes from \(i\) to \(j\) magically become equal to \(d\)“. Due to replacement of one numbers in array with others is performed, role of the set \(M\) can be also played by the set of integers \(\{-1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000\}\).
    Now, because sets \(G\) and \(M\) are known, we can define function-modifier \(f\), which modifies one number by replacing it with other:
    \(\forall g \in G\), \(\forall m \in M\): \(f \left( g, m \right) = m\).

The obtained elements of the model of the task:
\(G\) \(=\) \(\mathbb{Z}\)
\(\circ\) \(=\) \(+\)
\(M\) \(=\) \(\{-1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000\}\)
\(\forall g \in G\), \(\forall m \in M\): \(f \left( g, m \right) = m\)

An attentive reader will ask the question, why the set \(G\) was not defined as set \(\{-1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000\}\), because in the statement of the task elements of array are exactly elements of the set \(\{-1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000\}\). That’s because definition of the set \(G\) also depends on operation defined in it. If the set \(G\) would be defined as set \(\{-1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000\}\), it would not contain results of addition of elements of this set. I.e. for example the set \(G\) would not contain element \(n \cdot 1000\), which can be partial case of sum of all elements of the given array. But in fact by writing this text I’ve touched topic “Philosophy of interrelations of mathematics and programming”, so let’s continue.

2. Check of conditions of applicability of the universal segment tree

Actually, here are the conditions themselves from the Base Article:

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)\).

The set \(M_2\)

It’s easy to show, that neutral modifier \(e_M\) simply does not exist in the set \(M\). This follows from the definition from the function-modifier \(f\):
\(\forall g \in G\), \(\forall m \in M\): \(f \left( g, m \right) = m\)
From this definition it follows, that \(\forall g \in G\) \(f \left( g, e_M \right) = e_M\), and condition of the neutral modifier \(\forall g \in G\) \(f \left( g, e_{M} \right) = g\) can’t be satisfied.

So, because the neutral modifier does not exist, we require the definition of the neutral marker \(e_M\), which satisfies the only condition – \(e_M \notin M\). So, suppose \(e_M = 1001\).
Then \(M_2\) \(=\) \(M \cup \{ 1001 \}\) \(=\) \(\{ -1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000 \}\) \(\cup\) \(\{ 1001 \}\) \(=\) \(\{ -1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000, 1001 \}\)

So, \(M_2\) \(=\) \(\{ -1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000, 1001 \}\)

Conditions for the modifier-function \(f\)

  1. Combining function \(C\):
    Let’s define this function directly through the conditions of unification and condition of the neutral marker.

    • 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)\).
      Simplify the left and the right parts of condition, considering the definition of modifier-function \(f \left( g, m \right) = m\).
      Левая часть: \(f \left( a, {C \left( m_{1}, m_{2} \right)} \right)\) \(=\) \(C \left( m_{1}, m_{2} \right)\)
      Правая часть: \(f \left( {f \left( a, m_{1} \right)}, m_{2} \right)\) \(=\) \(f \left( m_{1}, m_{2} \right)\) \(=\) \(m_{2}\).
      Due to left part must equal to the right one, \(C \left( m_1, m_2 \right)\) \(=\) \(m_2\).
    • Condition of the neutral marker: the gotten due to the check of condition of unification function \(C \left( m_1, m_2 \right)\) \(=\) \(m_2\) satisfies condition of the neutral marker: \(C \left( e_M, m_2 \right)\) \(=\) \(m_2\).

    In result the formula for the function \(C\) is following: \(\forall m_1 \in M_2\), \(\forall m_2 \in M\), \(C \left( m_1, m_2 \right)\) \(=\) \(m_2\)

  2. Distributing function \(K\):
    So, suppose a given random 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. For the distributing function \(K\) the following condition must be satisfied:
    \(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)\)
    Due to \(\circ = +\), and \(\forall g \in G\), \(\forall m \in M\), \(f \left( g, m \right) = m\), we’ll get the following conversions in the condition:
    Left part: \(f \left( {a_{l} \circ a_{l+1} \circ \ldots \circ a_{r-1} \circ a_{r}}, {K \left( m, \delta \right)} \right)\) \(=\) \(K \left( m, \delta \right)\)
    Right part (consider, that it has \(\delta\) addends): \(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)\) \(=\) \(f \left( a_{l}, m \right) + f \left( a_{l+1}, m \right) + \ldots + f \left( a_{r-1}, m \right) + f \left( a_{r}, m \right)\) \(=\) \(m + m + \ldots + m + m\) \(=\) \(\delta \cdot m\).
    So, we’ve got the definition for the distributing function \(K\): \(K \left( m, \delta \right) = \delta \cdot m\)
  3. Extended function-modifier \(F\):
    By definition, \(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)\) \(=\) \(K \left( m, \delta \right)\) \(=\) \(\delta \cdot m\).
    So, \(F \left( {a_{l} + a_{l+1} + \ldots + a_{r-1} + a_{r}}, m, \delta \right) = \delta \cdot m\)

Due to all conditions of applicability of segment tree have been satisfied, the segment tree of multiple modifications is really applicable for the given task, and one can proceed to the last step of solution.

3. Programming

On this step everything comes down to the usage of the segment tree with instruction, program description of functions \(C\), \(F\) and operation \(\circ = +\), and other little things, connected with the statement of the task. I will only say, that segment tree in the shown below program is being built with method read – the segment tree calls given to this method function preprocessor() and reads the elements of given in the statement array one by one.

The program can be viewed here:

Solution with included code of the segment tree

Solution without code of segment tree