Binary Index Tree & Segment Tree Summary C++ Solution


  • 0
    F

    Count of Smaller Numbers After Self

    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> t, res(nums.size());
            for (int i = nums.size() - 1; i >= 0; i--) {
                int d = distance(t.begin(), lower_bound(t.begin(), t.end(), nums[i]));
                res[i] = d;
                t.insert(t.begin() + d, nums[i]);
            }
            return res;
        }
    };
    

    Count of Smaller Numbers Before Self

    class Solution {
    public:
        vector<int> countOfSmallerNumberII(vector<int>& A) {
            vector<int> t, res(A.size());
            for (int i = 0; i <= static_cast<int>(A.size()) - 1; i++) {
                int d = distance(t.begin(), lower_bound(t.begin(), t.end(), A[i]));
                res[i] = d;
                t.insert(t.begin() + d, A[i]);
            }
            return res;
        }
    };
    

    Build Segment Tree 1 & 2

    class Solution {
    public:
        /**
         *@param start, end: Denote an segment / interval
         *@return: The root of Segment Tree
         */
        SegmentTreeNode * build(int start, int end) {
            // write your code here
            if (start > end)    return NULL;
            SegmentTreeNode* root = new SegmentTreeNode(start, end);
            if (start == end)  return root;
            int mid=(start+end)/2;
            root->left = build(start, mid);
            root->right = build(mid+1, end);
            return root;
        }
    };
    

    Support record the max value of the corresponding interval max value :

    Segment tree build 2

    class Solution {
    public:
        /**
         *@param A: a list of integer
         *@return: The root of Segment Tree
         */
        SegmentTreeNode * build(vector<int>& A) {
            return buildRecu(A, 0, A.size() - 1);
        }
    
        SegmentTreeNode *buildRecu(const vector<int>& A, 
                                   const int start, const int end) {
            if (start > end) {
                return nullptr;
            }
            // The root's start and end is given by build method.
            SegmentTreeNode *root = new SegmentTreeNode(start, end, INT_MAX);
    
            // If start equals to end, there will be no children for this node.
            if (start == end) {
                root->max = A[start];
                return root;
            }
    
            // Left child: start=A.left, end=(A.left + A.right) / 2.
            root->left = buildRecu(A, start, (start + end) / 2);
    
            // Right child: start=(A.left + A.right) / 2 + 1, end=A.right.
            root->right = buildRecu(A, (start + end) / 2 + 1, end);
    
            const int left_max = root->left != nullptr ? root->left->max : INT_MAX;
            const int right_max = root->right != nullptr ? root->right->max : INT_MAX;
    
            // Update max.
            root->max = max(left_max, right_max);
            return root;
        }
    };
    

    Segment Tree Query 1 & 2

    Segment Tree Query 1

    class Solution {
    public:
        /**
         *@param root, start, end: The root of segment tree and
         *                         an segment / interval
         *@return: The maximum number in the interval [start, end]
         */
        int query(SegmentTreeNode *root, int start, int end) {
            // Out of range.
            if (root == nullptr || root->start > end || root->end <  start) {
                return INT_MIN;
            }
    
            // Current segment is totally within range [start, end]
            if (root->start >= start && root->end <= end) {
                return root->max;
            }
    
            int left = query(root->left, start, end);
            int right = query(root->right, start, end);
    
            // Find max in the children.
            return max(left, right);
        }
    };
    

    Segment Tree Query 2

    class Solution {
    public:
        /**
         *@param root, start, end: The root of segment tree and
         *                         an segment / interval
         *@return: The count number in the interval [start, end]
         */
        int query(SegmentTreeNode *root, int start, int end) {
            // Out of range.
            if (root == nullptr || root->start > end || root->end <  start) {
                return 0;
            }
    
            // Current segment is totally within range [start, end]
            if (root->start >= start && root->end <= end) {
                return root->count;
            }
    
            int left = query(root->left, start, end);
            int right = query(root->right, start, end);
    
            // Find max in the children.
            return left + right;
        }
    };
    

    Segment Tree Modify

    class Solution {
    public:
        /**
         *@param root, index, value: The root of segment tree and
         *@ change the node's value with [index, index] to the new given value
         *@return: void
         */
        void modify(SegmentTreeNode *root, int index, int value) {
            // Out of range.
            if (root == nullptr || root->start > index || root->end < index) {
                return;
            }
    
            // Change the node's value with [index, index] to the new given value.
            if (root->start == index && root->end == index) {
                root->max = value;
                return;
            }
    
            modify(root->left, index, value);
            modify(root->right, index, value);
    
            int left_max = root->left != nullptr? root->left->max : INT_MIN;
            int right_max = root->right != nullptr? root->right->max : INT_MIN;
    
            // Update max.
            root->max = max(left_max, right_max);
        }
    };
    
    

    Interval Sum--1

    Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the sum number between index start and end in the given array, return the result list.

    /**
     * Definition of Interval:
     * classs Interval {
     *     int start, end;
     *     Interval(int start, int end) {
     *         this->start = start;
     *         this->end = end;
     *     }
     */
    class SegmentTreeSumNode {
    public:
        int start, end;
        long long sum;
        SegmentTreeSumNode *left, *right;
        SegmentTreeSumNode(int start, int end, long long sum) {
            this->start = start;
            this->end = end;
            this->sum = sum;
            this->left = this->right = NULL;
        }
    };
    
    class Solution {
    public:
        /**
         *@param A, queries: Given an integer array and an query list
         *@return: The result list
         */
        vector<long long> intervalSum(vector<int> &A, vector<Interval> &queries) {
            vector<long long> res;
    
            // Build segment tree.
            SegmentTreeSumNode *root = build(A, 0, A.size() - 1);
    
            // Do each query.
            for (const auto& q : queries) {
                res.emplace_back(query(root, q.start, q.end));
            }
    
            return res;
        }
    
    
        // Build segment tree.
        SegmentTreeSumNode *build(vector<int> &A, int start, int end) {
            if (start > end) {
                return nullptr;
            }
    
            // The root's start and end is given by build method.
            SegmentTreeSumNode *root = new SegmentTreeSumNode(start, end, 0);
    
            // If start equals to end, there will be no children for this node.
            if (start == end) {
                root->sum = A[start];
                return root;
            }
    
            // Left child: start=A.left, end=(A.left + A.right) / 2.
            root->left = build(A, start, (start + end) / 2);
    
            // Right child: start=(A.left + A.right) / 2 + 1, end=A.right.
            root->right = build(A, (start + end) / 2 + 1, end);
    
            long long left_sum = root->left != nullptr? root->left->sum : 0;
            long long right_sum = root->right != nullptr? root->right->sum : 0;
    
            // Update sum.
            root->sum = left_sum + right_sum;
            return root;
        }
    
    
        // Query sum in given range.
        long long query(SegmentTreeSumNode *root, int start, int end) {
            // Out of range.
            if (root == nullptr || root->start > end || root->end <  start) {
                return 0;
            }
    
            // Current segment is totally within range [start, end]
            if (root->start >= start && root->end <= end) {
                return root->sum;
            }
    
            long long left = query(root->left, start, end);
            long long right = query(root->right, start, end);
    
            // Find sum in the children.
            return left + right;
        }
    };
    

    Interval Sum--2

    Given an integer array in the construct method, implement two methods query(start, end) and modify(index, value):
    For query(start, end), return the sum from index start to index end in the given array.
    For modify(index, value), modify the number in the given index to value

    class SegmentTreeSumNode {
    public:
        int start, end;
        long long sum;
        SegmentTreeSumNode *left, *right;
        SegmentTreeSumNode(int start, int end, long long sum) {
            this->start = start;
            this->end = end;
            this->sum = sum;
            this->left = this->right = NULL;
        }
    };
    
    class Solution {
    public:
        /* you may need to use some attributes here */
        SegmentTreeSumNode *root_;
    
        /**
         * @param A: An integer vector
         */
        Solution(vector<int> A) {
            root_ = build(A, 0, A.size() - 1);
        }
    
        /**
         * @param start, end: Indices
         * @return: The sum from start to end
         */
        long long query(int start, int end) {
            queryTree(root_, start, end);
        }
    
        /**
         * @param index, value: modify A[index] to value.
         */
        void modify(int index, int value) {
            modifyTree(root_, index, value);
        }
    
        // Query Sum in given range.
        long long queryTree(SegmentTreeSumNode *root, int start, int end) {
            // Out of range.
            if (root == nullptr || root->start > end || root->end <  start) {
                return 0;
            }
    
            // Current segment is totally within range [start, end]
            if (root->start >= start && root->end <= end) {
                return root->sum;
            }
    
            long long left = queryTree(root->left, start, end);
            long long right = queryTree(root->right, start, end);
    
            // Find sum in the children.
            return left + right;
        }
    
    
        void modifyTree(SegmentTreeSumNode *root, int index, int value) {
            // Out of range.
            if (root == nullptr || root->start > index || root->end < index) {
                return;
            }
    
            // Change the node's value with [index, index] to the new given value.
            if (root->start == index && root->end == index) {
                root->sum = value;
                return;
            }
    
            modifyTree(root->left, index, value);
            modifyTree(root->right, index, value);
    
            int left_sum = root->left != nullptr? root->left->sum : 0;
            int right_sum = root->right != nullptr? root->right->sum : 0;
    
            // Update sum.
            root->sum = left_sum + right_sum;
        }
    
        // Build segment tree.
        SegmentTreeSumNode *build(vector<int> &A, int start, int end) {
            if (start > end) {
                return nullptr;
            }
    
            // The root's start and end is given by build method.
            SegmentTreeSumNode *root = new SegmentTreeSumNode(start, end, 0);
    
            // If start equals to end, there will be no children for this node.
            if (start == end) {
                root->sum = A[start];
                return root;
            }
    
            // Left child: start=A.left, end=(A.left + A.right) / 2.
            root->left = build(A, start, (start + end) / 2);
            // Right child: start=(A.left + A.right) / 2 + 1, end=A.right.
            root->right = build(A, (start + end) / 2 + 1, end);
    
            long long left_sum = root->left != nullptr? root->left->sum : 0;
            long long right_sum = root->right != nullptr? root->right->sum : 0;
    
            // Update sum.
            root->sum = left_sum + right_sum;
            return root;
        }
    };
    
    

    Interval Minimum Number

    Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the minimum number between index start and end in the given array, return the result list.

    class SegmentTreeMinNode {
    public:
        int start, end, min;
        SegmentTreeMinNode *left, *right;
        SegmentTreeMinNode(int start, int end, int min) {
            this->start = start;
            this->end = end;
            this->min = min;
            this->left = this->right = NULL;
        }
    };
    
    class Solution {
    public:
        /**
         *@param A, queries: Given an integer array and an query list
         *@return: The result list
         */
        vector<int> intervalMinNumber(vector<int> &A, vector<Interval> &queries) {
            vector<int> res;
    
            // Build segment tree.
            SegmentTreeMinNode *root = build(A, 0, A.size() - 1);
    
            // Do each query.
            for (const auto& q : queries) {
                res.emplace_back(query(root, q.start, q.end));
            }
    
            return res;
        }
    
    
        // Build segment tree.
        SegmentTreeMinNode *build(vector<int> &A, int start, int end) {
            if (start > end) {
                return nullptr;
            }
    
            // The root's start and end is given by build method.
            SegmentTreeMinNode *root = new SegmentTreeMinNode(start, end, INT_MAX);
    
            // If start equals to end, there will be no children for this node.
            if (start == end) {
                root->min = A[start];
                return root;
            }
    
            // Left child: start=A.left, end=(A.left + A.right) / 2.
            root->left = build(A, start, (start + end) / 2);
    
            // Right child: start=(A.left + A.right) / 2 + 1, end=A.right.
            root->right = build(A, (start + end) / 2 + 1, end);
    
            int left_min = root->left != nullptr ? root->left->min : INT_MAX;
            int right_min = root->right != nullptr ? root->right->min : INT_MAX;
    
            // Update min.
            root->min = min(left_min, right_min);
            return root;
        }
    
    
        // Query min in given range.
        int query(SegmentTreeMinNode *root, int start, int end) {
            // Out of range.
            if (root == nullptr || root->start > end || root->end < start) {
                return INT_MAX;
            }
    
            // Current segment is totally within range [start, end]
            if (root->start >= start && root->end <= end) {
                return root->min;
            }
    
            const int left = query(root->left, start, end);
            const int right = query(root->right, start, end);
    
            // Find min in the children.
            return min(left, right);
        }
    };
    

Log in to reply
 

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