When you first read about segment trees, you probably wondered "why binary tree? why not ternary?". Let's start by analyzing segment tree's time complexity. It is $O(\log_{2}{n})$ . Or is it?

We will start with a normal segtree ( segment tree ), which supports range query and point update. To query on a range we break our segment into several subsegments $\left[l, r\right]$ which satisfy:

\begin{aligned} k \in \textbf{N} \\ x = 2^k \\ x | l \\ l+x=r+1 \end{aligned}

You can easily see that you need at most $2\log_2 n$ subsegments for a query $\left[l, r\right], r-l+1=n$ .

By setting $l=1$ , let's see the decomposition as $r$ varies:

\begin{aligned} r=1, [1, 1] \\ r=3, [1, 1], [2, 3] \\ r=7, [1, 1], [2, 3], [4, 7] \\ r=8, [1, 1], [2, 3], [4, 7], [8, 8] \\ \end{aligned}

But look what happens when we set $r=2 \cdot 7 = 14$ :

r=14, [1, 1], [2, 3], [4, 7], [8, 11], [12, 13], [14, 14]

We used $2$ times as many nodes as $r=7$ . Infact for all $r=2 \cdot (2^k-1), k \in \textbf{N}$ , we will need $2k$ subsegments! The proof that this is the worst case is left as an exercise for the reader.

Now let's find the maximum number of subsegments for a ternary segment tree. Again let's set $l=1$ :

\begin{aligned} r=1, [1, 1] \\ r=2, [1, 1], [2, 2] \\ r=8, [1, 1], [2, 2], [3, 5], [6, 8] \\ r=26, [1, 1], [2, 2], [3, 5], [6, 8], [9, 17], [18, 26] \\ r=16, [1, 1], [2, 2], [3, 5], [6, 8], [9, 11], [12, 14], [15, 15], [16, 16] \end{aligned}

And again the worst cases are $r=2 \cdot (3^k-1), k \in \textbf{N}$ . But now we use $4k$ subsegments instead of $2k$ . So for a given $r$ a binary tree will use at most $2 \lfloor \log_2 r \rfloor$ , and a ternary tree $4 \lfloor \log_3 r \rfloor$ .

By repeating the same process for an arbitrary $n$ -ary tree, we will see that the worst case is $r = 2 \cdot (n^k-1), k \in \textbf{N}$ , and we will use $2 \cdot (n - 1) \cdot k$ subsegments. We now replace $k=\log_n N$ . From that the answer seems simple: find the best $n$ such that $2 \cdot (n - 1) \cdot \log_n N$ is minimized for arbitrary $N$ . We can rewrite it removing the constant as

\begin{aligned} 2 \cdot (n - 1) \cdot \frac{\ln n}{\ln N} \\ \frac{2 \cdot (n - 1)}{\ln n} \end{aligned}

And the solution to that is: $1$ . We must've made a mistake. We didn't include the updates! Without updates of course the smaller the tree, the less nodes we have to query, and if the whole tree is $1$ node, then for each query we use only $1$ node. And the cost of a point update in an $n$ -ary tree is $\log_n N$ . If we assume the number of updates and queries is equal we get

\begin{aligned} \frac{2 \cdot (n - 1)}{\ln n} + \frac{1}{\ln n} \\ \frac{2n - 1}{\ln n} \end{aligned}

And the solution to that is: $2.16$ ! Meaning that a $2.16$ -ary segment tree is optimal IF the number of queries is equal to the number of updates. But let's solve it if the number of queries is $Q$ times the number of updates:

\begin{aligned} f(n) &= Q \cdot \frac{2n-2}{\ln n} + \frac{1}{\ln n} \\ f(n) &= \frac{Q(2n - 2) + 1}{\ln n} \\ u(n) &= Q(2n - 2) + 1 \\ v(n) &= \ln n \\ u'(n) &= 2Q \\ v'(n) &= \frac{1}{n} \\ f'(n) &= \frac{2Q \cdot \ln n - \left[ Q(2n - 2) + 1 \right] \cdot \frac{1}{n}}{(\ln n)^2} \\ f'(n) &= 0 \\ 2Q \cdot \ln n - \left[ Q(2n - 2) + 1 \right] \cdot \frac{1}{n} &= 0 \\ 2Q \cdot \ln n - 2Q+ \frac{2Q}{n} - \frac{1}{n} &= 0 \\ 2Q \cdot n \ln n - 2Qn + 2Q - 1 &= 0 \\ n \ln n - n + 1 - \frac{1}{2Q} &= 0 \end{aligned}

This equation is impossible to solve using standard arithmetic, and the proof is again left as an exercise for the reader. But it is absolutely possible numericaly. For example the newton method. To do it we need to find the derivative of $n \ln n - n + 1 - \frac{1}{2Q}$ : $\ln n$ . Now using a simple python script

Python

Pyodide

Output

Run the code to see the output.

So returning to the question at the start: if there are a lot more updates than queries, than a ternary tree will be better than binary!