自学内容网 自学内容网

【五十六】【算法分析与设计】线段树之add+query操作,pair表示节点,自定义类型表示节点,真树结构实现线段树与数组实现线段树

线段树解决的问题

给你一个nums数组,1.L~R区间上的值全部加C。2.L~R区间上的值全部变成C。3.对L~R区间上求和操作。

对于第一个方法,如果正常遍历L~R加C,时间复杂度是O(N)。

对于第二个方法,如果正常遍历L~R=C,时间复杂度是O(N)。

对于第三个方法,如果正常遍历L~R得到sum累加和,时间复杂度是O(N)。

线段树可以做到O(logN)时间复杂度做到这三个方法。

线段树

nums数组对应的线段树构造

我有一个nums数组,3,2,1,2,6,下标依次从1开始,分别是1,2,3,4,5

我构建一个sum数组,sum数组下标为1的位置,表示nums数组1~5的累加和。

对于sum数组任意一个位置i,左孩子的下标一定是2*i,右孩子的下标一定是2*i+1,父亲的下标一定是i/2。

对于sum数组任意一个位置i,包含的信息是nums数组中l~r区间上的和,在sum数组的下标是i。

左孩子包含的信息是nusm数组中l~mid区间上的和,在sum数组的下标是i*2。其中mid=(l+r)>>1=(l+r)/2。

左孩子包含的信息是nusm数组中mid+1~r区间上的和,在sum数组的下标是i*2+1。其中mid=(l+r)>>1=(l+r)/2。

lazy懒数组

1.

lazy懒数组是一个和sum数组大小一样,并且树结构、下标一一对应的数组。也可以看作是sum数组的另一个信息的存储。

如果sum数组中不存放int类型,而是存储结构体类型或者pair类型,使得每一个节点都可以存放两个信息,lazy懒数组就可以省去,因为它表示的信息以及存在了每一个节点中,不需要再来一个数组与之绑定。

2.

lazy懒数组存储的是任务,例如我想要add(L,R,C,)操作,将nums数组中L~R区间上的值都统一加C。

此时我更新的不是nums数组,而是sum数组。

我需要把sum数组中所有位置的数据都维护好。

例如我希望将nums数组中4~5位置上的值都统一加2。

那么我需要维护的位置是1、3、6、7,四个位置。

6、7位置的sum值实际上不需要维护,因为到3位置的时候,3位置表示的是4~5的区间和,这个区间在任务区间内,因此维护3位置的sum值,lazy[3]=2。此时存储任务,懒得下发任务。

因此需要维护得位置只有1和3。

3.

什么时候可以懒住任务,什么时候不能懒住任务?

当我当前得节点信息表示得区间是 l~r,这个区间被任务区间包含在内,即L<=l&&r<=R的时候就可以懒住任务不再下发。反正则不能懒住任务。

pushup函数

 
        void pushup(int rt) {
                sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
        }

如果我左右孩子sum值维护好了,调用pushup函数维护当前节点rt的sum值。

pushudown函数

 
        void pushdown(int rt, int ln, int rn) {
                if (lazy[rt] != 0) {
                        lazy[rt << 1] += lazy[rt];
                        lazy[rt << 1 | 1] += lazy[rt];
                        sum[rt << 1] += lazy[rt] * ln;
                        sum[rt << 1 | 1] += lazy[rt] * rn;
                        lazy[rt] = 0;
                }
        }

将当前节点的任务下发一层,维护好执行完任务后的sum值,注意此时只是下发一层,也就是让下一层执行任务并且懒住。因为当前节点懒住的任务,说明当前节点的区间 l~r一定全部被L~R包含,那么当前节点的左右孩子也一定全部被L~R包含。所以让孩子执行任务后懒住任务。

add(L,R,C)对nums数组区间统一加C操作

 
        void _add(int L, int R, int C, int l, int r, int rt) {//维护rt节点的sum值,如果可以懒就懒,不可以懒就不懒,不懒的时候需要发任务维护下一层sum
                if (r < L || R < l) return;
                if (L <= l && r <= R) {
                        sum[rt] += C * (r - l + 1);
                        lazy[rt] += C;
                        return;
                }
                int mid = (l + r) >> 1;
                pushdown(rt, mid - l + 1, r - (mid + 1) + 1);

                _add(L, R, C, l, mid, rt << 1);
                _add(L, R, C, mid + 1, r, rt << 1 | 1);
                pushup(rt);
        }

_add(L,R,C,l,r,rt)递归函数,表示将nums数组中L~R区间全部加上C,nums对应的sum树当前节点的信息是 l~r区间和,在sum数组中下标是rt。

递归函数定义是,维护当前rt位置的sum值,如果任务能懒则懒,懒不住就递归到下一层节点,重复操作,能懒则懒。

如果当前节点区间范围不在L~R范围内,也就是没有一个重合区间,直接返回。

如果当前节点区间范围在L~R范围内,并且是所有元素都在这个L~R区间内,说明可以懒住任务。此时直接维护当前节点的sum值,然后维护当前节点的lazy值,返回即可,任务懒住不再下发。

如果上面两种情况没中,说明此时 l~r区间有一部分在L~R范围内,有一部分不在L~R范围内。此时先把当前节点存放的任务下发一层,意思是当前节点存放的任务,让下一层维护好sum值。然后将当前任务下发到下一层,维护好sum值。

让孩子执行完懒住的任务并且维护好sum后,还需要让孩子执行新的任务维护sum值,能不能懒住再看具体情况。

执行完这两个任务之后,左右孩子的sum值一定维护好了,pushup维护当前节点的sum值。

当左右孩子sum值维护好,用他们的值维护自己即可。

query(L,R)查询nums数组区间和操作

 
        int _query(int L, int R, int l, int r, int rt) {//返回区间和,包裹住了就整个返回,不能就分开加和返回,分开加和需要把任务下发维护下一层sum
                if (r < L || R < l) {
                        return 0;
                }
                if (L <= l && r <= R) {
                        return sum[rt];
                }
                int mid = (l + r) >> 1;
                pushdown(rt, mid - l + 1, r - (mid + 1) + 1);
                return _query(L, R, l, mid, rt << 1) + _query(L, R, mid + 1, r, rt << 1 | 1);
        }

我需要查询L~R区间的累加和,递归函数_query表示任务是查询L~R区间和,当前节点信息是nums数组l~r区间和,再sum数组中下标是rt。

如果当前节点区间范围不在L~R范围内,也就是没有一个重合区间,直接返回 0。

如果当前节点区间范围在L~R范围内,并且是所有元素都在这个L~R区间内,说明此时节点的sum值是我们需要的,直接返回sum[rt]。

如果当前节点区间范围有一部分在L~R范围内,一部分不在L~R范围内,将当前任务下发一层,让孩子节点做任务,然后懒住任务,这一步表示维护好下一层的sum值,维护好之后,当前层的sum值等于左右孩子sum值的和。

sum数组,lazy数组需要开多大的空间?

将nums数组离散化成树状数组,nums大小是size,sum和lazy开辟4*size空间即可。

小总结

1.

add操作和query操作,每一次访问某一个节点的时候,该节点的sum值一定是维护好的。

2.

add操作,我当前节点的范围 l~r在L~R内部,全部都在内部,说明当前树的值整个需要维护,但是我只维护根节点的值,任务懒住不下发给子树。

add操作,如果当前节点的范围 l~r一部分在L~R内,一部分不在,我只需要更新在内部的sum值,我一定能在子树中找到一棵树,表示的区间 l~r全部位于L~R内,并且所有这样的树的范围合并起来,一定是完整的L~R。

我只需要维护每一棵这样的树的根sum值,然后懒住任务不下发。

3.

query操作,我当前节点的范围 l~r在L~R内部,全部都在内部,说明当前树的值整个是我需要用到的值,并且当前sum值是维护好的,我直接返回即可。

query操作,如果当前节点的范围 l~r一部分在L~R内,一部分不在,我一定能在子树中找到一棵树,表示的区间 l~r全部位于L~R内,并且所有这样的树的范围合并起来,一定是完整的L~R。

所有树的sum值得累加我就我们需要得结果。

线段树代码

查询区间和+区间add (模板)

 
class SegmentTree {//查询区间和+区间add (模板)
private:
        vector<int> sum;
        vector<int> lazy;
        int size;

        void pushup(int rt) {
                sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
        }

        void pushdown(int rt, int ln, int rn) {
                if (lazy[rt] != 0) {
                        lazy[rt << 1] += lazy[rt];
                        lazy[rt << 1 | 1] += lazy[rt];
                        sum[rt << 1] += lazy[rt] * ln;
                        sum[rt << 1 | 1] += lazy[rt] * rn;
                        lazy[rt] = 0;
                }
        }

        void _add(int L, int R, int C, int l, int r, int rt) {//维护rt节点的sum值,如果可以懒就懒,不可以懒就不懒,不懒的时候需要发任务维护下一层sum
                if (r < L || R < l) return;
                if (L <= l && r <= R) {
                        sum[rt] += C * (r - l + 1);
                        lazy[rt] += C;
                        return;
                }
                int mid = (l + r) >> 1;
                pushdown(rt, mid - l + 1, r - (mid + 1) + 1);

                _add(L, R, C, l, mid, rt << 1);
                _add(L, R, C, mid + 1, r, rt << 1 | 1);
                pushup(rt);
        }

        int _query(int L, int R, int l, int r, int rt) {//返回区间和,包裹住了就整个返回,不能就分开加和返回,分开加和需要把任务下发维护下一层sum
                if (r < L || R < l) {
                        return 0;
                }
                if (L <= l && r <= R) {
                        return sum[rt];
                }
                int mid = (l + r) >> 1;
                pushdown(rt, mid - l + 1, r - (mid + 1) + 1);
                return _query(L, R, l, mid, rt << 1) + _query(L, R, mid + 1, r, rt << 1 | 1);
        }

public:
        SegmentTree(int _size) {
                size = _size;
                sum.resize(size << 2);
                lazy.resize(size << 2);
        }
        void add(int L, int R, int C) {
                _add(L, R, C, 0, size, 1);//区间一一对应,0~size-1 
        }
        int query(int L, int R) {
                return _query(L, R, 0, size, 1);//区间一一对应,0~size-1 
        }
};


int main() {
        vector<int> nums = { 1,2,3,4,5,6,7,8,9,10 };
        SegmentTree st(nums.size());
        for (int i = 0; i < nums.size(); i++)
                st.add(i, i, nums[i]);

        cout << st.query(0, nums.size() - 1) << endl;
        cout << accumulate(nums.begin(), nums.end(), 0) << endl;
}

查询区间和+区间add(pair代替lazy数组)

 

class SegmentTree {
private:
        int size;
        vector<pair<int, int>> node;//first---sum,second---lazy

        void pushup(int rt) {
                node[rt].first = node[rt << 1].first + node[rt << 1 | 1].first;
        }
        void pushdown(int rt, int ln, int rn) {
                if (node[rt].second != 0) {
                        int c = node[rt].second;
                        node[rt].second = 0;

                        node[rt << 1].first += c;
                        node[rt << 1 | 1].first += c;
                        node[rt << 1].second += c;
                        node[rt << 1 | 1].second += c;
                }
        }

        void _add(int L, int R, int C, int l, int r, int rt) {
                if (r < L || R < l) {
                        return;
                }
                if (L <= l && r <= R) {
                        node[rt].first += C;
                        node[rt].second += C;
                        return;
                }
                int mid = (l + r) >> 1;
                pushdown(rt, mid - l + 1, r - (mid + 1) + 1);
                _add(L, R, C, l, mid, rt << 1);
                _add(L, R, C, mid + 1, r, rt << 1 | 1);
                pushup(rt);
        }

        int _query(int L, int R, int l, int r, int rt) {
                if (r < L || R < l) {
                        return 0;
                }
                if (L <= l && r <= R) {
                        return node[rt].first;
                }

                int mid = (l + r) >> 1;
                pushdown(rt, mid - l + 1, r - (mid + 1) + 1);
                return _query(L, R, l, mid, rt << 1) + _query(L, R, mid + 1, r, rt << 1 | 1);
        }

public:
        SegmentTree(int n) {
                size = n;
                node.resize(size << 2);
        }

        void add(int L, int R, int C) {
                _add(L, R, C, 0, size - 1, 1);
        }

        int query(int L, int R) {
                return _query(L, R, 0, size - 1, 1);
        }
};


int main() {
        vector<int> nums = { 1,2,3,4,5,6,7,8,9,10 };
        SegmentTree st(nums.size());
        for (int i = 0; i < nums.size(); i++) {
                st.add(i, i, nums[i]);
        }

        cout << st.query(0, nums.size() - 1) << endl;
        cout << accumulate(nums.begin(), nums.end(), 0) << endl;
        cout << st.query(0, 5) << endl;
        cout << accumulate(nums.begin(), nums.begin() + 5 + 1, 0) << endl;
}

查询区间和+区间add(自定义类型表示node)

 

class SegmentTree {
private:
        struct Node {
                int sum;
                int lazy;
        };
        vector<Node> node;
        int size;

        void pushup(int rt) {
                node[rt].sum = node[rt << 1].sum + node[rt << 1 | 1].sum;
        }

        void pushdown(int rt, int ln, int rn) {
                if (node[rt].lazy != 0) {
                        int c = node[rt].lazy;
                        node[rt].lazy = 0;

                        node[rt << 1].sum += c;
                        node[rt << 1].lazy += c;
                        node[rt << 1 | 1].sum += c;
                        node[rt << 1 | 1].lazy += c;
                }
        }

        void _add(int L, int R, int C, int l, int r, int rt) {
                if (r < L || R < l) {
                        return;
                }
                if (L <= l && r <= R) {
                        node[rt].sum += C;
                        node[rt].lazy += C;
                        return;
                }

                int mid = (l + r) >> 1;
                pushdown(rt, mid - l + 1, r - (mid + 1) + 1);

                _add(L, R, C, l, mid, rt << 1);
                _add(L, R, C, mid + 1, r, rt << 1 | 1);
                pushup(rt);
        }

        int _query(int L, int R, int l, int r, int rt) {
                if (r < L || R < l) {
                        return 0;
                }
                if (L <= l && r <= R) {
                        return node[rt].sum;
                }

                int mid = (l + r) >> 1;
                pushdown(rt, mid - l + 1, r - (mid + 1) + 1);

                return  _query(L, R, l, mid, rt << 1) +
                        _query(L, R, mid + 1, r, rt << 1 | 1);

        }

public:
        SegmentTree(int n) {
                size = n;
                node.resize(size << 2);
        }

        void add(int L, int R, int C) {
                _add(L, R, C, 0, size - 1, 1);
        }

        int query(int L, int R) {
                return _query(L, R, 0, size - 1, 1);
        }
};


int main() {
        vector<int> nums = { 1,2,3,4,5,6,7,8,9,10 };
        SegmentTree st(nums.size());
        for (int i = 0; i < nums.size(); i++) {
                st.add(i, i, nums[i]);
        }

        cout << st.query(0, nums.size() - 1) << endl;
        cout << accumulate(nums.begin(), nums.end(), 0) << endl;
        cout << st.query(0, 5) << endl;
        cout << accumulate(nums.begin(), nums.begin() + 5 + 1, 0) << endl;
}

查询区间和+区间add(真树结构)

 

class SegmentTreeNode {
public:
    int start, end, sum, lazy;
    SegmentTreeNode* left;
    SegmentTreeNode* right;

    SegmentTreeNode(int start, int end) : start(start), end(end), sum(0), lazy(0), left(nullptr), right(nullptr) {}
};

class SegmentTree {
private:
    SegmentTreeNode* root;

    SegmentTreeNode* buildTree(vector<int> nums, int start, int end) {
        if (start > end) {
            return nullptr;
        }
        SegmentTreeNode* node = new SegmentTreeNode(start, end);
        if (start == end) {
            node->sum = nums[start];
        } else {
            int mid = start + (end - start) / 2;
            node->left = buildTree(nums, start, mid);
            node->right = buildTree(nums, mid + 1, end);
            node->sum = node->left->sum + node->right->sum;
        }
        return node;
    }

    void addHelper(SegmentTreeNode* node, int L, int R, int C) {
        if (!node || node->end < L || node->start > R) {
            return;
        }
        if (node->start >= L && node->end <= R) {
            node->sum += C;
            node->lazy += C;
            return;
        }
        int mid = node->start + (node->end - node->start) / 2;
        addHelper(node->left, L, R, C);
        addHelper(node->right, L, R, C);
        node->sum = (node->left ? node->left->sum : 0) + (node->right ? node->right->sum : 0);
    }

    int queryHelper(SegmentTreeNode* node, int L, int R) {
        if (!node || node->end < L || node->start > R) {
            return 0;
        }
        if (node->start >= L && node->end <= R) {
            return node->sum;
        }
        int mid = node->start + (node->end - node->start) / 2;
        return queryHelper(node->left, L, R) + queryHelper(node->right, L, R);
    }

public:
    SegmentTree(int n) {
        root = buildTree(vector<int>(n, 0), 0, n - 1);
    }

    void add(int L, int R, int C) {
        addHelper(root, L, R, C);
    }

    int query(int L, int R) {
        return queryHelper(root, L, R);
    }
};

int main() {
    vector<int> nums = { 1,2,3,4,5,6,7,8,9,10 };
    SegmentTree st(nums.size());

    for (int i = 0; i < nums.size(); i++) {
        st.add(i, i, nums[i]);
    }

    cout << st.query(0, nums.size() - 1) << endl;
    cout << accumulate(nums.begin(), nums.end(), 0) << endl;
    cout << st.query(0, 5) << endl;
    cout << accumulate(nums.begin(), nums.begin() + 5 + 1, 0) << endl;

    return 0;
}

结尾

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

谢谢您的支持,期待与您在下一篇文章中再次相遇!


原文地址:https://blog.csdn.net/m0_74163972/article/details/137964168

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!