Advertisement
Guest User

Untitled

a guest
Jun 19th, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.80 KB | None | 0 0
  1. 1st element is a query for value 6, as Fenwick tree is empty -> result is 0
  2. 2nd is element 5 -> add index 0 into Fenwick tree
  3. 3rd element is 4 -> add index 1 into tree.
  4. 4th element is 3 -> add index 4 into tree.
  5. 5th element is 2 -> add index 2 into tree.
  6. 6th element is query for range (2, 5), we query the tree and get answer 2.
  7. 7th element is 1 -> add index 3 into tree.
  8. Finish.
  9.  
  10. count = m-j;
  11.  
  12. i=0; for (j=1;j<=m;j<<=1;); j>>=1;
  13.  
  14. [9 4 5 6 1 3 2 8] Node 1
  15. [9 4 5 6] [1 3 2 8] Node 2-3
  16. [9 4] [5 6] [1 3] [2 8] Node 4-7
  17. [9] [4] [5] [6] [1] [3] [2] [8] Node 8-15
  18.  
  19. [1 2 3 4 5 6 8 9] Node 1
  20. [4 5 6 9] [1 2 3 8] Node 2-3
  21. [4 9] [5 6] [1 3] [2 8] Node 4-7
  22. [9] [4] [5] [6] [1] [3] [2] [8] Node 8-15
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement