Why do we require a 4*n memory for each of the answer array and the flag array in segment tree with lazy propogation.Can not we work with 2*n memory for each of these arrays and also can not we do this thing that instead of using a flag in the parent node for indicating that it's children needs to be updated we set the flag in the children itself indicating that these needs to be updated.
Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены.
→ Обратите внимание
До соревнования
Spectral::Cup 2026 Round 2 (Codeforces Round 1100, Div. 1 + Div. 2)
19:58:43
Зарегистрироваться »
Spectral::Cup 2026 Round 2 (Codeforces Round 1100, Div. 1 + Div. 2)
19:58:43
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3844 |
| 2 | Benq | 3792 |
| 3 | tourist | 3719 |
| 4 | VivaciousAubergine | 3647 |
| 5 | jiangly | 3616 |
| 6 | ksun48 | 3595 |
| 7 | Kevin114514 | 3491 |
| 8 | strapple | 3486 |
| 9 | Um_nik | 3376 |
| 10 | turmax | 3371 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.05.2026 21:36:18 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Please can anyone explain why do we need 4*N memory for segment tree construction ?
Actually we don't. It just makes the things easier.
Actually we just need
2N - 1nodes, where N >= n is a power of 2In the worst case it is 4*n if n = 2k + 1
so your bound is actually higher (n = 2k + 1, N = 2k + 1, 2N - 1 = 2k + 2 - 1 = 4n - 5) :D
n = 2k + 1 ------------ 4n = 2(k + 2) + 4 ------------ 2(k + 2) - 1 = 4n - 5
Really higher :D
this is what i do. here is my code to solve HORRIBLE on SPOJ. if u dont understand it, u can post a comment here.
ok i have understood that but i have tried to solve a question by this method but it's giving runtime error. can you please help me in this? i am tired of fixing the bug but still not succeded here is the problem link :http://mirror.codeforces.com/problemset/problem/242/E and here is my code:http://mirror.codeforces.com/submissions/vis10326#.i will be greatly thankful to you
format ur code a bit better (a few spaces and tabs in each line should be enough).
also, give a link to ur submission in question, not ur submissions page.
Do you have real eyes?