线段树#创作计划#

蛟龙_湖风

2026-07-04 14:28:23

发布于：浙江

42阅读

0回复

0点赞

线段树的构建:

typedef long long ll;
void build(ll p, ll l, ll r) {  // 根节点  左节点  右节点
    // 将左端点和右端点的数据放入到p节点下
    tree[p].l = l;
    tree[p].r = r;
    tree[p].MutiLazyTag = 1;         // 对于乘法懒标记初始化为1
    if (l == r) {            // 当前是叶子节点
        tree[p].value = arr[l];  // 放入值 arr[r]
        return;              // 结束
    }
    int mid = (l + r) / 2;                                  //(l+r)>>1  找出中间值
    build(p * 2, l, mid);                                   // 构建左子树
    build(p * 2 + 1, mid + 1, r);                           // 构建右子树
    tree[p].value = (tree[p * 2].value + tree[p * 2 + 1].value) % mod;  // 回溯
}

区间查询:

ll query(ll p, int x, int y) {  // 根节点   左节点   右节点
    // 当前查询的p点的区间被x和y全包含
    if (x <= tree[p].l && y >= tree[p].r) {
        // 返回包含的值
        return tree[p].value;
    }
    lazy_tag_transport(p);  // 懒标记下传
    // 二分范围
    int mid = (tree[p].l + tree[p].r) / 2;  // 当前节点左右 去划分
    ll flag = 0;
    if (x <= mid) {
        flag += query(p * 2, x, y);  // 去左子树取值
        flag %= mod;
    }
    // 左右可能都有值需要去取
    if (y > mid) {
        flag += query(p * 2 + 1, x, y);  // 去右子树取值
        flag %= mod;
    }
    return flag;
}

懒标记(Lazy Tag)区间修改:

struct node{ // 结构体的形式构建线段树
    int l, r, value;  // 左节点的起始点 右节点终点(l->r:p节点所包含的范围)
    int AddlazyTag, MutiLazyTag; // 懒标记
};
void lazy_tag_transport(ll p) {  // 懒标记下传
    tree[p * 2].value = tree[p].MutiLazyTag * tree[p * 2].value + (tree[p * 2].r - tree[p * 2].l + 1) * tree[p].AddLazyTag;
    tree[p * 2].value %= mod;
    tree[p * 2 + 1].value = tree[p].MutiLazyTag * tree[p * 2 + 1].value + (tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1) * tree[p].AddLazyTag;
    tree[p * 2 + 1].value %= mod;

    tree[p * 2].MutiLazyTag *= tree[p].MutiLazyTag;
    tree[p * 2].MutiLazyTag %= mod;
    tree[p * 2 + 1].MutiLazyTag *= tree[p].MutiLazyTag;
    tree[p * 2 + 1].MutiLazyTag %= mod;

    tree[p * 2].AddLazyTag = tree[p].MutiLazyTag * tree[p * 2].AddLazyTag + tree[p].AddLazyTag;
    tree[p * 2].AddLazyTag %= mod;
    tree[p * 2 + 1].AddLazyTag = tree[p].MutiLazyTag * tree[p * 2 + 1].AddLazyTag + tree[p].AddLazyTag;
    tree[p * 2 + 1].AddLazyTag %= mod;
    tree[p].AddLazyTag = 0;   // 清空上一层的懒标记  已经传输完毕了
    tree[p].MutiLazyTag = 1;  // 乘法懒标记清空为1
}
void AddZoneupdate(ll p, ll x, ll y, ll z) {  // 区间修改   根节点  需要修改的范围  需要修改的值
    // 找出需要修改的位置
    if (x <= tree[p].l && y >= tree[p].r) {            // tree[p].value+=z;
        tree[p].value += (tree[p].r - tree[p].l + 1) * z;  // 对于找到的位置进行修改(给x的位置增加)   tree[p].value = z;
        tree[p].AddLazyTag += z;                               // 懒标记也要加
        tree[p].value %= mod;
        tree[p].AddLazyTag %= mod;
        return;
    }
    lazy_tag_transport(p);                                                 // 懒标记下传
    tree[p].value = (tree[p * 2].value + tree[p * 2 + 1].value) % mod;  // 回溯
    // 二分范围
    int mid = (tree[p].l + tree[p].r) / 2;  // 当前节点左右 去划分
    // 查询当前需要找的位置是在左半边还是右半边
    if (x <= mid)
        AddZoneupdate(p * 2, x, y, z);
    if (y > mid)
        AddZoneupdate(p * 2 + 1, x, y, z);
    tree[p].value = (tree[p * 2].value + tree[p * 2 + 1].value) % mod;  // 回溯
}
void MutiZoneupdate(ll p, ll x, ll y, ll z) {  // 区间修改   根节点  需要修改的范围  需要修改的值
    // 找出需要修改的位置
    if (x <= tree[p].l && y >= tree[p].r) {  // tree[p].value+=z;
        tree[p].value *= z;                      // 对于当前的位置相乘
        tree[p].AddLazyTag *= z;                     // 懒标记也要乘
        tree[p].MutiLazyTag *= z;                    // 懒标记也要乘
        tree[p].value %= mod;
        tree[p].AddLazyTag %= mod;
        tree[p].MutiLazyTag %= mod;
        return;
    }
    lazy_tag_transport(p);                                                 // 懒标记下传
    tree[p].value = (tree[p * 2].value + tree[p * 2 + 1].value) % mod;  // 回溯
    // 二分范围
    int mid = (tree[p].l + tree[p].r) / 2;  // 当前节点左右 去划分
    // 查询当前需要找的位置是在左半边还是右半边
    if (x <= mid)
        MutiZoneupdate(p * 2, x, y, z);
    if (y > mid)
        MutiZoneupdate(p * 2 + 1, x, y, z);
    tree[p].value = (tree[p * 2].value + tree[p * 2 + 1].value) % mod;  // 回溯
}