Hello cf! I am solving this problem http://www.spoj.com/problems/HORRIBLE/ . And I don't know how to implement BIT with range modification. Please help me. Thanks.
№ | Пользователь | Рейтинг |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
2 | adamant | 164 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Hello cf! I am solving this problem http://www.spoj.com/problems/HORRIBLE/ . And I don't know how to implement BIT with range modification. Please help me. Thanks.
Название |
---|
You should read about Segment Tree. This blog relly helped me to understand it — segment tree!
there are great tutorial on russian: tutorial, you can translate it with any translator.
There is a variant of BIT Trees that does range_update & point_query we will use this one
To update a range [l, r] with value V (incrementing every element in range by V), we add V to bit[l] and subtract it from bit[r + 1], since bit tree returns for we always get the right results for point queries
Now in order to make range_queries and range_updates, lets have a look at our array a:
[0, 0, 0, 0, 0, 0]
Calling update(l = 3, r = 5, v = 5) should make it like this:
[0, 0, 5, 5, 5, 0]
And prefix_sum array: [0, 0, 5, 10, 15, 15]
Let's divide the array into 3 parts:
a[1, ..., l - 1] query(x) should return 0
a[l, ..., r] query(x) should return V × (x - (l - 1)) = Vx - V(l - 1)
a[r + 1, ..., N] query(x) should return V × (r - (l - 1)) = Vr - V(l - 1)
So basically, query(x) is now like a linear function of index x: f(x) = Ax + B
The terms that depend on x can be stored in a bit tree and other terms in another bit tree
Pseudo_code:
Wow, now it's clear for me, thank you ^^
But in function update_range(..) in second row u should write
update_point(bitAX, r+1, -v)
You are forgot a minus before "v" :)
UPD: fixed
Thanks, sorry for forgetting such important thing :D
Thank you for your perfect explanation! Is not query (r) -query (l-1) on the last line? I think it should be minus, not plus.
Yes! That should have been minus instead of plus.
Read this Blog : Various Usage Of BIT