LeetCode 370 线段树懒标记板子

维护区间和

class SegmentTree
{
public:
    struct Node{
        Node *left,*right;
        int start, end;
        int info;
        int tag;
        Node(int a, int b):start(a),end(b),info(0),tag(0),left(NULL),right(NULL){}
    };
    Node *root;
    SegmentTree(int a,int b){
        root=new Node(a,b);
        build(root,a,b);
    }
    void build(Node* node, int a, int b)  // init for range [a,b]
    {
        if (a==b)
        {
            node->info = 0;
            return;
        }
        int mid = (a+b)/2;

        node->left = new Node(a, mid);
        node->right = new Node(mid+1, b);

        build(node->left, a, mid);
        build(node->right, mid+1, b);
        pushUp(node);           // write your own logic
    }
    void pushUp(Node *node){
        node->info = node->left->info + node->right->info;  // write your own logic
    }
    void updateRangeBy(Node* node, int a, int b, int val)
    {
        if (b < node->start || a > node->end ) return;
        if (a <= node->start && node->end <=b)
        {
            // write your own logic
            node->info += val * len(node);
            node->tag += val;
            return;
        }

        pushDown(node);          // write your own logic
        int mid=(node->start+node->end)>>1;
        if(a<=mid) updateRangeBy(node->left, a, b, val);
        if(b>mid) updateRangeBy(node->right, a, b, val);

        pushUp(node);               // write your own logic
    }

    int len(Node* node)
    {
        return node->end - node->start + 1;
    }

    void pushDown(Node* node)
    {
        if (node->tag!=0)
        {
            node->left->info += len(node->left) * node->tag;
            node->left->tag += node->tag;
            node->right->info += len(node->right) * node->tag;
            node->right->tag += node->tag;
            node->tag = 0;
        }
    }

    int queryRange(Node* node, int a, int b)
    {
        if (a <= node->start && b>=node->end)
        {
            return node->info;  // write your own logic
        }
        pushDown(node);          // write your own logic
        int mid=(node->start+node->end)>>1;
        long long sum=0;
        if(a<=mid) sum+=queryRange(node->left, a, b);
        if(b>mid)  sum+=queryRange(node->right, a, b);
        return sum;   // write your own logic
    }
};
class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates)
    {
        SegmentTree* tree = new SegmentTree(0, length-1);

        for (auto& update: updates)
        {
            tree->updateRangeBy(tree->root,update[0], update[1], update[2]);
        }
        vector<int>rets(length);
        for (int i=0; i<length; i++)
            rets[i] = tree->queryRange(tree->root,i,i);
        return rets;
    }
};