Motivating problem: You have an array of size N with N different numbers; calculate the sum of the numbers in the interval of a to b.

What is the proof that a Segment Tree performs those queries in log(n) time? Or where can I find the proof? Thanks.

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

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

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

1 | Errichto | 201 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 186 |

6 | vovuh | 183 |

7 | Um_nik | 181 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

Motivating problem: You have an array of size N with N different numbers; calculate the sum of the numbers in the interval of a to b.

What is the proof that a Segment Tree performs those queries in log(n) time? Or where can I find the proof? Thanks.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/20/2021 16:35:30 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

The segment tree has

O(log(n))levels. The algorithm visitsat most O(1) nodes per levelduring the query, because of this:Let [L, R) be the interval covered by current vertex. Let denote # number covered by [a, b) and . the other nodes.

Only these situations can occur:

`..........`

`##########`

`#######...`

or`.......###`

`...#####..`

The situations 1 and 2 cost O(1) time.The situation 3 divides the interval into two smallers ones.

At most one of childrenwill have type 3, the others will be 1 or 2.`...#######`

->`...## + #####`

(3 -> 3, 2)`.......###`

->`..... + ..###`

(3 -> 1, 3)`.....#####`

->`..... + #####`

(3 -> 1, 2)The situation 4 can divide into:

`....#####..`

->`...## + ###..`

(4 -> 3, 3)`......##...`

->`..... + .##..`

(4 -> 1, 4)`.....###...`

->`..... + ###..`

(4 -> 1, 3)So there will be only

one child of type 4 orthere will beat most two children of type 3.At the beginning of query we have one of the stituations 1, 2, 3, 4 on top level. It is easy to see that there can be at most 1 node of type 4 per level and if there is no type 4 there can be at most two nodes of type 3 per level.

So there can be only

4 = O(1)nodes visited in each level (at most two of type {3,4})That means

O(log(n))visited nodes. Inside each node we spentO(1)time.I think Case 2 and 3 are interchangeably drawn.

Shouldn't case

2be`a <= L && R <= b`

? Because you said the whole interval`[L, R)`

is in interval`[a, b)`

. Anyway, this is by far the best time complexity analysis of segment tree that I have came across. Thanks :)Well, firstly, you have to build the tree in O(nlogn). Every vertex has: interval covered, sum-to-be-added and overall-sum. So when you go deeper if the interval searched is bigger than the covered you just get the sum. So in the worst case you will have query (a = n/2, b=n/2+1) for which you will go to 2 different leaves of the tree. This means 2*logn operations at most in one query. The sum-to-be-added value is used if you have updates for an interval for the same reason. When you reach a fully covered interval you update that value, so that you can use it in the queries by adding that value times the length of the answer to the result. PS: The update trick with sum-to-be added is called lazy propagation, so you can look for it on the net.

A short idea of lazy propagation:

Let's take the same type you propose, where queries are for sum of interval.

Imagine that you want to increase all the numbers in the interval corresponding to node

nbyx. You don't need to update the whole subtree; instead, just mark inn"for this subtree, each element is actually plusx". Now, you don't traverse deeper into the subtree anymore.Now, what happens if you need to traverse some of the nodes of this subtree later? You must pass through

n. And at that point, you can update the sons ofn— if all elements in the interval ofnare larger byx, then so will be all the elements in the intervals of the sons ofn(since those 2 together make the interval ofn). So, you just copy the information "for this subtree, each element is actually plusx" into the sons ofn.Now, you must make sure you won't repeat that again for the same information. In node

n, you remember the sum of its interval [z,k). Increase that sum byx* (k-z) (all thek-zelements are increased byx). And setx= 0. If there are more queries which end at noden,xcan be further modified.The details of how the updates are done differ slightly between different types of trees, but the overall idea stays the same: if you know that an operation is applied to a subtree, store it at the root.

It´s because a segment tree have log(n) levels, and in every step, if your querry is outside the interval of the node that you are you can discard this node, if all your querry is inside the interval of your node you return this sum, else you need to go to the next level. but if you see this, you will do this maximum 2 times for level, then your complexity will be 2(log(n)). :)