how to prove space complexity in segment tree is O(4*n).

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 184 |

2 | adamant | 178 |

3 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 152 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 149 |

how to prove space complexity in segment tree is O(4*n).

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/04/2023 04:20:41 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Segment tree with 2^x leaf nodes will have 2^(x+1) — 1 total nodes because it is a perfect binary tree.

Now, you will have useless leaf nodes if you are using general n. Therefore at worst you will have almost 2*n leaf nodes because you must round up to the next power of two. If n is 2^j + 1, then you must have 2^(j+1) leaf nodes = O(2*n).

And as we proved before total nodes is ~2 * leaf nodes so we have 2*2*n = O(4n) total space.

thanks for explanation. is there any other mathematical proof to prove this?

If you're not satisfied by the above proof here is another:

Last layer: nodes

Pre-last layer: nodes

So, we have nodes.

You can see the infinite geometric progression on the right. Its sum is equal to , where is first element of progression ( here) and is ratio between two adjacent elements ( here).

So, there is a total of nodes in a segment tree.

why would it be infinite G.P. on RHS? I mean it could be finite as well right?

if n is 2^j + 1 then the segment tree will have 2^(j+1) + 1 leaf nodes, not 2^(j+1)

This problem was one of the INOI 2012-2013 problems.At first note that we need

exactly2·n- 1 nodes, but if we use arrays and set id of left child of node with idIdto 2·Idand 2·Id+ 1 id to right one, we need an array with size 4·n, let's prove.Let

f(n) the maximumidthat we need in segment tree. Let's provef(2^{n}+ 1) = 4·2^{n}- 1. We can prove it using induction,f(2^{1}+ 1) = 7,f(2^{n}+ 1) = 2·f(2^{n - 1}+ 1) + 1 = 2·(4·2^{n - 1}- 1) + 1 = 4·2^{n}- 1.Edit: Definition off(n) has changed.Let

kbe the smallest natural number such that 2^{k}≥n. Note that 2^{k}< 2 ×n. We will find the answer for 2^{k}. The segment tree, and indeed any other binary tree formed will have exactlyk+ 1 levels, thei-th containing 2^{i}nodes. Then, the total number of nodes will be a geometric progression of the form 2^{0}+ 2^{1}+ 2^{2}+ ... + 2^{k}, which is precisely equal to 2^{k + 1}- 1. Since 2^{k}< 2 *n, it follows immediately that 2^{k + 1}- 1 < 4 ×n, so the number of nodes of the new tree — greater than our answer — is still less than 4 ×n.Non-recursive segment trees use exactly 2

n- 1 nodes.@AI.Cash: I've read u non-recursive segment tree. It's very easy, powerful as general segment-tree and required less memory space. But, in non-recursive segment tree how to find lower bound of position for given sum ?? // for perfect binary tree (i.e. n = 2^k):

when n = 2^k, this works fine, but n != 2^k not.

Indeed, for

n≠ 2^{k}we basically get not one tree butO(logn) separate perfect trees. So, it doesn't support the techniques where we need to start from the root and move to the leaves, like binary search and fractional cascading.Thx. I'll use O(4n) case with your implementation in this case.