getSum()

size_t getSum(int l, int r) {
    unsigned long long int diff = 0;
    int left_boundary = 0;
    int right_boundary = n_keys_;

    int i = 0;
    while(i < n_keys_ && keys_[i] < l) {
      ++i;
    }
    if(i == n_keys_) { //fully outside range from the left
      if(leaf_) {
        return 0;
      }
      return children_[n_keys_]->getSum(l, r);
    }
    left_boundary = i;

    i = n_keys_ - 1;
    while(i >= 0 && keys_[i] > r) {
      --i;
    }
    if(i == -1) {
      if(leaf_){
        return 0; //fully outside range from the right
      }
      return children_[0]->getSum(l, r);
    }
    right_boundary = i;

    if(keys_[0] >= l && keys_[n_keys_ - 1] <=r) // fully inside range
    {
      if(leaf_) {
        return sub_sum;
      }
      diff += children_[0]->sub_sum - children_[0]->getSum(l, r);
      diff += children_[n_keys_]->sub_sum - children_[n_keys_]->getSum(l, r);
      return sub_sum - diff;
    }

    if(right_boundary < left_boundary) {
      if(leaf_){
        return 0;
      }
      return children_[left_boundary]->getSum(l, r);
    }

    for(int i = 0; i < left_boundary; ++i) {
      diff += keys_[i];
      if(!leaf_) {
        diff += children_[i]->sub_sum;
      }
    }
    for(int i = n_keys_ - 1; i > right_boundary; --i) {
      diff += keys_[i];
      if(!leaf_) {
        diff += children_[i + 1]->sub_sum;
      }
    }

    if(!leaf_) {
      diff += children_[left_boundary]->sub_sum - children_[left_boundary]->getSum(l, r);
      diff += children_[right_boundary + 1]->sub_sum - children_[right_boundary + 1]->getSum(l, r);
    }
    return sub_sum - diff;
}