Advertisement
sleepy_coder

Binary Indexed Tree/ Fenwick Tree (C++ implementation)

Jan 24th, 2019
132
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.13 KB | None | 0 0
  1. struct BITree{
  2.     private:
  3.         long long *biTree;
  4.         unsigned int size_n;
  5.     public:
  6.  
  7.         BITree(){
  8.             this->biTree = nullptr;
  9.             this->size_n = 0;
  10.         }
  11.  
  12.         explicit BITree(int n) : size_n(static_cast<unsigned int>(n)) {
  13.             biTree = new long long[size_n+1];
  14.             for(int i = 0 ; i <= size_n; i++)
  15.                 biTree[i] = 0;
  16.         }
  17.  
  18.         BITree(const int *ara, int lo, int hi, int n) {
  19.             this->size_n = static_cast<unsigned int>(n);
  20.             biTree = new long long[size_n+1];
  21.             for(int i = 0; i <= size_n; i++)biTree[i] = 0LL;
  22.  
  23.             for(int i = lo, indx = 1 ; i <= hi ; i++, indx++){
  24.                 int val = ara[i], index = indx;
  25.                 while(index <= size_n){
  26.                     biTree[index] += val;
  27.                     index += index & -index;
  28.                 }
  29.             }
  30.         }
  31.  
  32.         BITree(const BITree& rhs){
  33.             this->size_n = rhs.size_n;
  34.             this->biTree = new long long[size_n + 1];
  35.  
  36.             for(int i = 0 ; i <= size_n; i++){
  37.                 this->biTree[i] = rhs.biTree[i];
  38.             }
  39.         }
  40.  
  41.         void init(const int *ara, int lo, int hi, int n){
  42.             delete [] biTree; biTree = nullptr;
  43.             size_n = 0;
  44.  
  45.             this->size_n = static_cast<unsigned int>(n);
  46.             biTree = new long long[size_n+1];
  47.             for(int i = 0; i <= size_n; i++)biTree[i] = 0;
  48.  
  49.             for(int i = lo, indx = 1 ; i <= hi ; i++, indx++){
  50.                 int val = ara[i], index = indx;
  51.                 while(index <= size_n){
  52.                     biTree[index] += val;
  53.                     index += index & -index;
  54.                 }
  55.             }
  56.         }
  57.  
  58.         BITree& operator=(const BITree& rhs){
  59.             delete [] biTree; biTree = nullptr;
  60.             size_n = 0;
  61.  
  62.             this->size_n = rhs.size_n;
  63.             this->biTree = new long long[size_n + 1];
  64.  
  65.             for(int i = 0 ; i <= size_n; i++){
  66.                 this->biTree[i] = rhs.biTree[i];
  67.             }
  68.  
  69.         }
  70.  
  71.         unsigned int size() const { return this->size_n; }
  72.  
  73.         bool empty() { return this->size() == 0; }
  74.  
  75.         long long getSumUpto(int indx){
  76.             long long currSum = 0;
  77.             while(indx > 0){
  78.                 currSum += biTree[indx];
  79.                 indx -= indx & -indx;
  80.             }
  81.             return currSum;
  82.         }
  83.  
  84.         void update(int indx, int val){
  85.             while(indx <= size_n){
  86.                 biTree[indx] += val;
  87.                 indx += indx & -indx;
  88.             }
  89.         }
  90.  
  91.         long long getRangedSum(int lo, int hi){
  92.             return getSumUpto(hi) - getSumUpto(lo-1);
  93.         }
  94.  
  95.         friend ostream &operator<<(ostream &os, const BITree &biTree) {
  96.             cout<< " n: " << biTree.size()<<endl;
  97.             os << " biTree: " ;
  98.             for(int i = 1 ; i <= biTree.size(); i++){
  99.                 os<<biTree.biTree[i]<<" ";
  100.             }
  101.             return os;
  102.         }
  103.  
  104.         virtual ~BITree() {
  105.             size_n = 0;
  106.             delete [] biTree;
  107.         }
  108.     };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement