Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 1st element is a query for value 6, as Fenwick tree is empty -> result is 0
- 2nd is element 5 -> add index 0 into Fenwick tree
- 3rd element is 4 -> add index 1 into tree.
- 4th element is 3 -> add index 4 into tree.
- 5th element is 2 -> add index 2 into tree.
- 6th element is query for range (2, 5), we query the tree and get answer 2.
- 7th element is 1 -> add index 3 into tree.
- Finish.
- count = m-j;
- i=0; for (j=1;j<=m;j<<=1;); j>>=1;
- [9 4 5 6 1 3 2 8] Node 1
- [9 4 5 6] [1 3 2 8] Node 2-3
- [9 4] [5 6] [1 3] [2 8] Node 4-7
- [9] [4] [5] [6] [1] [3] [2] [8] Node 8-15
- [1 2 3 4 5 6 8 9] Node 1
- [4 5 6 9] [1 2 3 8] Node 2-3
- [4 9] [5 6] [1 3] [2 8] Node 4-7
- [9] [4] [5] [6] [1] [3] [2] [8] Node 8-15
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement