You are not logged in. Please login at www.codechef.com to post your questions!

×

Range Update in BIT

Is it possible to update a range in Binary Indexed Tree...?? I want this to solve the http://www.codechef.com/problems/FLIPCOIN problem using Binary Indexed Tree(BIT).

asked 06 Feb '13, 20:25

saikrishna173's gravatar image

3★saikrishna173
1757916
accept rate: 9%


I've explained range updates with BIT and provided implementation here: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/

link

answered 02 Dec '13, 22:26

kartikkukreja's gravatar image

5★kartikkukreja
1064
accept rate: 16%

Really amazing post!! :D It helped me understanding some things in a pratical way which I've only read about! Thanks!

(04 Dec '13, 06:23) kuruma2★

hey ..did studied ur post bt could not understand "Why we are not doing :- update(a,v) update(b+1,-v) for the update part and query(b)-query(a-1) for the sum part ..whats wrong in that part???"

(04 Apr '14, 09:40) wonder2★
link

answered 02 Jul '13, 18:30

sparshgunner12's gravatar image

4★sparshgunner12
1.1k51021
accept rate: 10%

link

answered 13 Dec '13, 03:23

chandan721's gravatar image

3★chandan721
2013919
accept rate: 0%

I have spent many days to understand range update, wrote simple explanation with example here: https://github.com/manoharreddyporeddy/AdvancedDataStructuresAndAlgorithms/blob/master/BIT_fenwick_tree_explanation.md

link

answered 05 Nov, 07:37

pgmreddy's gravatar image

0★pgmreddy
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×522
×136
×52
×7

question asked: 06 Feb '13, 20:25

question was seen: 10,806 times

last updated: 05 Nov, 07:37