C++ BST solution


  • 0
    N
    typedef long long LL;
    struct Tree{
        struct Node {
            LL k;
            int le;
            Node* l;
            Node* r;
            
            Node(LL k){
                l = 0;
                r = 0;
                this->k = k;
                this->le = 1;
            }
        };
        
        Node* root;
        
        Tree(){
            root = new Node(0);
        }
        
        void insert(LL k){
            Node* cur = root;
            Node* prev = 0;
            while(cur){
                if(cur->k == k){
                    cur->le++;
                    return;
                }
                if(cur->k < k){
                    prev = cur;
                    cur = cur->r;
                } else {
                    prev = cur;
                    cur->le++ ;
                    cur = cur->l;
                }
            }
            if(k > prev->k){
                prev->r = new Node(k);
            } else {
                prev->l = new Node(k);
            }
        }
        int sum_le(LL k){
            Node* cur = root;
            int res = 0;
            while(cur){
                if(cur->k==k){
                    res += cur->le;
                    break;
                } else if(cur->k < k){
                    res += cur->le;
                    cur = cur->r;
                } else {
                    cur = cur->l;
                }
            }
            return res;
        }
    };
    
    class Solution {
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            Tree t;
            LL s = 0;
            int res = 0;
            for(int i=0;i<nums.size();++i){
                s += nums[i];
                
                int p = t.sum_le(s-lower);
                int q = t.sum_le(s-upper-1);
                res += p-q;
                
                t.insert(s);
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.