线段树优化 - 从基础代码到更简洁高效实现

本文将比较两种线段树的实现方式，从基础的结构体+lazytag实现到更简洁高效的数组+懒标记实现，并提供C++代码示例，方便读者理解和学习。

基础实现：结构体+lazytag

以下代码展示了线段树的基本实现，使用了结构体来存储节点信息，并使用lazytag来维护懒标记。

#include <iostream>
#include <cstdio>
using namespace std;
//题目中给的p
int p;
//暂存数列的数组
long long a[100007];
//线段树结构体，v表示此时的答案，mul表示乘法意义上的lazytag，add是加法意义上的
struct node{
    long long v, mul, add;
}st[400007];
//buildtree
void bt(int root, int l, int r){
//初始化lazytag
    st[root].mul=1;
    st[root].add=0;
    if(l==r){
        st[root].v=a[l];
    }
    else{
        int m=(l+r)/2;
        bt(root*2, l, m);
        bt(root*2+1, m+1, r);
        st[root].v=st[root*2].v+st[root*2+1].v;
    }
    st[root].v%=p;
    return ;
}
//核心代码，维护lazytag
void pushdown(int root, int l, int r){
    int m=(l+r)/2;
//根据我们规定的优先度，儿子的值=此刻儿子的值*爸爸的乘法lazytag+儿子的区间长度*爸爸的加法lazytag
    st[root*2].v=(st[root*2].v*st[root].mul+st[root].add*(m-l+1))%p;
    st[root*2+1].v=(st[root*2+1].v*st[root].mul+st[root].add*(r-m))%p;
//很好维护的lazytag
    st[root*2].mul=(st[root*2].mul*st[root].mul)%p;
    st[root*2+1].mul=(st[root*2+1].mul*st[root].mul)%p;
    st[root*2].add=(st[root*2].add*st[root].mul+st[root].add)%p;
    st[root*2+1].add=(st[root*2+1].add*st[root].mul+st[root].add)%p;
//把父节点的值初始化
    st[root].mul=1;
    st[root].add=0;
    return ;
}
//update1，乘法，stdl此刻区间的左边，stdr此刻区间的右边，l给出的左边，r给出的右边
void ud1(int root, int stdl, int stdr, int l, int r, long long k){
//假如本区间和给出的区间没有交集
    if(r<stdl || stdr<l){
        return ;
    }
//假如给出的区间包含本区间
    if(l<=stdl && stdr<=r){
        st[root].v=(st[root].v*k)%p;
        st[root].mul=(st[root].mul*k)%p;
        st[root].add=(st[root].add*k)%p;
        return ;
    }
//假如给出的区间和本区间有交集，但是也有不交叉的部分
//先传递lazytag
    pushdown(root, stdl, stdr);
    int m=(stdl+stdr)/2;
    ud1(root*2, stdl, m, l, r, k);
    ud1(root*2+1, m+1, stdr, l, r, k);
    st[root].v=(st[root*2].v+st[root*2+1].v)%p;
    return ;
}
//update2，加法，和乘法同理
void ud2(int root, int stdl, int stdr, int l, int r, long long k){
    if(r<stdl || stdr<l){
        return ;
    }
    if(l<=stdl && stdr<=r){
        st[root].add=(st[root].add+k)%p;
        st[root].v=(st[root].v+k*(stdr-stdl+1))%p;
        return ;
    }
    pushdown(root, stdl, stdr);
    int m=(stdl+stdr)/2;
    ud2(root*2, stdl, m, l, r, k);
    ud2(root*2+1, m+1, stdr, l, r, k);
    st[root].v=(st[root*2].v+st[root*2+1].v)%p;
    return ;
}
//访问，和update一样
long long query(int root, int stdl, int stdr, int l, int r){
    if(r<stdl || stdr<l){
        return 0;
    }
    if(l<=stdl && stdr<=r){
        return st[root].v;
    }
    pushdown(root, stdl, stdr);
    int m=(stdl+stdr)/2;
    return (query(root*2, stdl, m, l, r)+query(root*2+1, m+1, stdr, l, r))%p;
}
int main(){
    int n, m;
    scanf("%d%d%d", &n, &m, &p);
    for(int i=1; i<=n; i++){
        scanf("%lld", &a[i]);
    }
    bt(1, 1, n);
    while(m--){
        int chk;
        scanf("%d", &chk);
        int x, y;
        long long k;
        if(chk==1){
            scanf("%d%d%lld", &x, &y, &k);
            ud1(1, 1, n, x, y, k);
        }
        else if(chk==2){
            scanf("%d%d%lld", &x, &y, &k);
            ud2(1, 1, n, x, y, k);
        }
        else{
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(1, 1, n, x, y));
        }
    }
    return 0;
}

更简洁高效的实现：数组+懒标记

以下代码展示了另一种实现方式，使用数组来存储节点信息，并使用懒标记数组来维护懒标记。这种实现方式更加简洁高效，并且更容易理解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int lSon(int k) { return k << 1; }
int rSon(int k) { return (k << 1) + 1; }
int getM(int s, int e) { return s + ((e - s) >> 1); }

int n, m;
ll a[N], tree[N << 2], add[N];

void built(int s, int e, int k)
{
    if (s == e)
    {
        tree[k] = a[s];
        return;
    }
    int m = getM(s, e);
    built(s, m, lSon(k)), built(m + 1, e, rSon(k));
    tree[k] = tree[lSon(k)] + tree[rSon(k)];
}

ll getsum(int l, int r, int s, int e, int k)
{
    if (l <= s && e <= r)
    {
        return tree[k];
    }
    int m = getM(s, e);
    ll res = 0;
    if (add[k])
    {
        tree[lSon(k)] += add[k] * (m - s + 1), tree[rSon(k)] += add[k] * (e - m);
        add[lSon(k)] += add[k], add[rSon(k)] += add[k];
        add[k] = 0;
    }
    if (l <= m)
    {
        res += getsum(l, r, s, m, lSon(k));
    }
    if (r > m)
    {
        res += getsum(l, r, m + 1, e, rSon(k));
    }
    return res;
}

void update(int l, int r, ll d, int s, int e, int k)
{
    if (l <= s && e <= r)
    {
        tree[k] += (e - s + 1) * d, add[k] += d;
        return;
    }
    int m = getM(s, e);
    if (add[k] && s != e)
    {
        tree[lSon(k)] += add[k] * (m - s + 1), tree[rSon(k)] += add[k] * (e - m);
        add[lSon(k)] += add[k], add[rSon(k)] += add[k];
        add[k] = 0;
    }
    if (l <= m)
    {
        update(l, r, d, s, m, lSon(k));
    }
    if (r > m)
    {
        update(l, r, d, m + 1, e, rSon(k));
    }
    tree[k] = tree[lSon(k)] + tree[rSon(k)];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }
    built(1, n, 1);
    while (m--)
    {
        int cmd;
        scanf("%d", &cmd);
        if (cmd == 1)
        {
            int x, y;
            ll k;
            scanf("%d%d%lld", &x, &y, &k);
            update(x, y, k, 1, n, 1);
        }
        else
        {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%lld\n", getsum(x, y, 1, n, 1));
        }
    }
    return 0;
}

总结

两种实现方式各有优劣：

• 结构体+lazytag 实现更易于理解，但代码相对繁琐。
• 数组+懒标记 实现更简洁高效，但理解难度略高。

建议读者根据自己的需求选择合适的实现方式。

本文仅供参考，希望能够帮助读者更好地理解和学习线段树。