Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct BITree{
- private:
- long long *biTree;
- unsigned int size_n;
- public:
- BITree(){
- this->biTree = nullptr;
- this->size_n = 0;
- }
- explicit BITree(int n) : size_n(static_cast<unsigned int>(n)) {
- biTree = new long long[size_n+1];
- for(int i = 0 ; i <= size_n; i++)
- biTree[i] = 0;
- }
- BITree(const int *ara, int lo, int hi, int n) {
- this->size_n = static_cast<unsigned int>(n);
- biTree = new long long[size_n+1];
- for(int i = 0; i <= size_n; i++)biTree[i] = 0LL;
- for(int i = lo, indx = 1 ; i <= hi ; i++, indx++){
- int val = ara[i], index = indx;
- while(index <= size_n){
- biTree[index] += val;
- index += index & -index;
- }
- }
- }
- BITree(const BITree& rhs){
- this->size_n = rhs.size_n;
- this->biTree = new long long[size_n + 1];
- for(int i = 0 ; i <= size_n; i++){
- this->biTree[i] = rhs.biTree[i];
- }
- }
- void init(const int *ara, int lo, int hi, int n){
- delete [] biTree; biTree = nullptr;
- size_n = 0;
- this->size_n = static_cast<unsigned int>(n);
- biTree = new long long[size_n+1];
- for(int i = 0; i <= size_n; i++)biTree[i] = 0;
- for(int i = lo, indx = 1 ; i <= hi ; i++, indx++){
- int val = ara[i], index = indx;
- while(index <= size_n){
- biTree[index] += val;
- index += index & -index;
- }
- }
- }
- BITree& operator=(const BITree& rhs){
- delete [] biTree; biTree = nullptr;
- size_n = 0;
- this->size_n = rhs.size_n;
- this->biTree = new long long[size_n + 1];
- for(int i = 0 ; i <= size_n; i++){
- this->biTree[i] = rhs.biTree[i];
- }
- }
- unsigned int size() const { return this->size_n; }
- bool empty() { return this->size() == 0; }
- long long getSumUpto(int indx){
- long long currSum = 0;
- while(indx > 0){
- currSum += biTree[indx];
- indx -= indx & -indx;
- }
- return currSum;
- }
- void update(int indx, int val){
- while(indx <= size_n){
- biTree[indx] += val;
- indx += indx & -indx;
- }
- }
- long long getRangedSum(int lo, int hi){
- return getSumUpto(hi) - getSumUpto(lo-1);
- }
- friend ostream &operator<<(ostream &os, const BITree &biTree) {
- cout<< " n: " << biTree.size()<<endl;
- os << " biTree: " ;
- for(int i = 1 ; i <= biTree.size(); i++){
- os<<biTree.biTree[i]<<" ";
- }
- return os;
- }
- virtual ~BITree() {
- size_n = 0;
- delete [] biTree;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement