fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. class FenwickTree
  7. {
  8.     //createTree: which fill the binaryIndexTree array where the required values are stored and manipulated;
  9.     //updateTree: which is used to insert of update a value of index 'i' from the source array which is done at index i+1 of the binaryIndexTree
  10.     //getSum : provide the sum upto a particular index of the array 
  11.     //getParent: provide the parent of a index 'i';
  12.     //getNext: provides index of the childs and other nodes affected by changing an index 'i'
  13.     int* binaryIndexedTree=NULL;
  14.     int len = 0;
  15.  
  16.     public:
  17.     FenwickTree(int arr[], int arrsize)
  18.     {
  19.         this->len = arrsize + 1;
  20.         cout << "len: " << len << endl;
  21.         this->binaryIndexedTree = new int[len];
  22.  
  23.  
  24.         createTree(arr);
  25.     }
  26.  
  27.     void createTree(int arr[])
  28.     {
  29.         for(int i=0; i<len; i++) binaryIndexedTree[i] = 0;
  30.         binaryIndexedTree[0] = 0;
  31.         for(int i=1 ; i<len; i++)
  32.         {
  33.             updateTree(arr[i-1], i);
  34.         }
  35.     }
  36.  
  37.     void updateTree(int value, int index)
  38.     {
  39.         cout << "Inside uptate";
  40.         while(index < len)
  41.         {
  42.             binaryIndexedTree[index] += value;
  43.             index = getNext(index);
  44.         }
  45.     }
  46.     //Step 1: Calculate 2's complement of index
  47.     //Step 2: DO Logical AND with the original index;
  48.     //Step 3 : Add the above got value with the original index
  49.     int getNext(int index)
  50.     {
  51.         return index + (index & -index);
  52.     }
  53.  
  54.     //Step 1: Calculate 2's complement of index
  55.     //Step 2: DO Logical AND with the original index;
  56.     //Step 3 : Add the above got value with the original index
  57.     int getParent(int index)
  58.     {
  59.         return index - (index & -index);
  60.     }
  61.  
  62.     int getSum(int index)
  63.     {
  64.         cout << "inside get sum";
  65.         index = index + 1;
  66.         int sum = 0;
  67.         while(index > 0)
  68.         {
  69.             sum += binaryIndexedTree[index];
  70.             index = getParent(index);
  71.         }
  72.         for(int i=0; i<len; i++) cout << binaryIndexedTree[i] << " ";
  73.         cout << endl;
  74.         return sum;
  75.     }
  76.  
  77.     void updateTreeWithElement(int value, int index)
  78.     {
  79.         index = index + 1;
  80.         int diff_to_propagate = value - binaryIndexedTree[index];
  81.  
  82.         while(index < len)
  83.         {
  84.             binaryIndexedTree[index] += diff_to_propagate;
  85.             index = getNext(index);
  86.         }
  87.     }
  88. };
  89.  
  90. int main()
  91. {
  92.  
  93.     int input[] = {1,2,3,4,5,6,7};
  94.  
  95.     FenwickTree* ft = new FenwickTree(input, sizeof(input)/sizeof(input[0]));
  96.  
  97.     ft->updateTreeWithElement(6, 4);
  98.  
  99.     ft->updateTreeWithElement(4, 4);
  100.  
  101.     int ans = ft->getSum(5);
  102.  
  103.     cout << "ans: " << ans << endl;
  104.  
  105.  
  106.  
  107.  
  108.     return 0;
  109. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
len: 8
Inside uptateInside uptateInside uptateInside uptateInside uptateInside uptateInside uptateinside get sum0 1 3 3 10 4 10 7 
ans: 20
https://ideone.com/4QSUep
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!