Help with Segment Tree

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
27:09:32
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя viesis

Help with Segment Tree

Автор viesis, 9 лет назад, По-английски

Hello all,

I have read segment tree, lazy propagation tutorials. but I find difficult to solve some problems like this one. Can anyone give more necessary tutorials or problems links to master segment tree?

Thanks in advance.

viesis
9 лет назад
15

Комментарии (10)

Показать архивные | Написать комментарий?

mrz

9 лет назад, # |

Algorithm Gym :: Everything About Segment Trees This is a very good tutorial. Enjoy it !!

→ Ответить

tenshi_kanade

9 лет назад, # |

← Rev. 2 →

That problem can be solved with a self-balancing BST in O(N_logN) or with a segment tree in O(N_log²N) as far as I know.

→ Ответить

Hand1e

9 лет назад, # ^ |

There is a O(NlogN) solution with segment tree.

→ Ответить

tenshi_kanade

9 лет назад, # ^ |

← Rev. 2 →

You're right, I didn't give it much time. When you traverse the tree, you decide to go left or right depending on the number of elements on each interval, so it's N_logN effectively. I was actually thinking in the O(N_log²N) solution using BIT when I said "segment tree".

→ Ответить

viesis

9 лет назад, # ^ |

Hi, I had an idea, but I am terrible at implementation, so can you help ensuring if my approach will be correct? or Is there any valid similar approach?

01. In the tree we will take a cnt variable where we will save how many items we have removed so far till the current position.
02. While removing an item from position pos we will increase the cnt value by 1 from pos to end position.
03. In the array we will always save value in their previous position(1 based index).
04. For example let the array is A[] = {2,3,4,5,6}
05. The cnt value in the tree is cnt[] = {0,0,0,0,0}
06. If the query is (c,2) cnt[2] = 0; So we will print A[2+0] which is 3.Update from (2+0) to End by increasyng cnt value by 1 and set A[2+0] = -1.
07. Now A[] = {2,-1,4,5,6} and cnt[] = {0,1,1,1,1}
08. If the query is (a,5) we add this to the end of array.
09. Now A[] = {2,-1,4,5,6,5} and cnt[] = {0,1,1,1,1,1}
10. If the query is (c,3) cnt[3] = 1; So we will print A[3+1] which is 5.Update from (3+1) to End by increasyng cnt value by 1 and set A[3+1] = -1.
11. Now A[] = {2,-1,4,-1,6,5} and cnt[] = {0,1,1,2,2,2}

Thanks!

→ Ответить

tenshi_kanade

9 лет назад, # ^ |

If at the end of all your steps, you get a query (c,3), you have cnt[3] = 1, so you will print A[3+1] = -1, while the correct answer is to print A[5]. With BIT, you would need to do O(_log²N) per query, though you can achieve O(_logN) using segment tree by storing in each node the total number of people in that range.

→ Ответить