Can somebody explain “Range Updates And Range Queries in BIT”?
Can’t Understand…Please Help…
BIT is binary indexed tree(fenwick tree) ??
Yeah In Binary Indexed Tree.
Hi @avik26091998,
I recommend you to do it in this sequence:
- Understand BIT
https://www.youtube.com/watch?v=CWDQJGaN1gY - Range Query logic
http://codeforces.com/blog/entry/619 - Just code a simple inplementation
https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/ - Code a slightly complicated one
https://www.hackerearth.com/practice/notes/binary-indexed-tree-made-easy-2/ - You cannot become good at it unless you code it multiple times. So it’s okay to study the code from the above sites and write it on paper, if need help then check the code again.
- Repeat 3-5 until you are able to code it perfectly without referring the reference material.
- Solve these to improve your concepts
https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/practice-problems/ - Upvote this post if you liked it
1 Like
@obi1 great post.
Can you suggest such a post for segment tree. I know basic of segment trees like rmq, point update.
Hi @pavitra_ag,
I personally am not very good with segment trees but I can suggest you the approach I took to get started.
- Tushar Roy’s basics
https://www.youtube.com/watch?v=ZBHKZF5w4YU - Lazy propogation
https://www.youtube.com/watch?v=xuoQdt5pHj0 - Fast Iterative implementation of segment tree
http://codeforces.com/blog/entry/18051 - Recursive segment tree
https://www.hackerearth.com/practice/notes/segment-trees-for-beginners/ - What I personally refer to
https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/ - There’s simply no substitute to just solving it again and again using pen and paper(kinda fun doing in class when the lecture going on is pretty boring)
- I am currently solving these to get the hang of it
https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/
1 Like