小樱の博客

菜单

樱序
发布于 2026-10-15 / 3 阅读
0
0

线段树

线段树1

如题，已知一个数列 {ai​}，你需要进行下面两种操作：

  1. 将某区间每一个数加上 k。

  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 n,m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数 ai​，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 [x,y] 内每个数加上 k。

  2. 2 x y：输出区间 [x,y] 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

#include<bits/stdc++.h>
using namespace std;
long long tree[400005];
long long a[400005],lazy[400005];
void pushdown(int node, int l, int r){
    if(lazy[node] == 0){
        return;
    }
    int mid = (l+r)/2;
    tree[node*2] += lazy[node]*(mid - l + 1);
    lazy[node*2] += lazy[node];
    
    tree[node*2+1] += lazy[node]*(r - mid);
    lazy[node*2+1] += lazy[node];

    lazy[node] = 0;
}
void update(int node, int l, int r, int ql, int qr, long long k){
    if(ql<=l && qr >= r){
        tree[node] += k*(r-l+1);
        lazy[node] += k;
        return;
    }
    pushdown(node, l, r);
    int mid = (l+r)/2;
    if(ql <= mid){
        update(2*node,l,mid,ql,qr,k);
    }
    if(qr > mid){
        update(2*node+1,mid+1,r,ql,qr,k);
    }
    tree[node]=tree[node*2+1]+tree[node*2];
    
}
void build(int node, int l, int r){
    int mid = (l+r)/2;
    if(l==r){
        tree[node] = a[l];
        return;
    }
    build(node*2, l, mid);
    build(node*2+1, mid+1, r);
    tree[node] = tree[node*2+1] + tree[node*2];
}
long long query(int node, int l, int r, int ql, int qr){
    if(ql <= l && qr >= r){//目前检索的序列完全包含于最终需要的
        return tree[node];
    }
    pushdown(node,l,r);
    int mid = (l+r)/2;
    long long ans = 0;
    if(ql <= mid){
        ans += query(2*node, l, mid,ql, qr);
    }
    if(qr >mid){
        ans += query(2*node+1, mid + 1, r, ql, qr);
    }
    return ans;
}
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    build(1,1,n);
    while(m--){
        int t;
        cin>>t;
        if(t == 1){
            long long x,y,k;
            cin>>x>>y>>k;
            update(1,1,n,x,y,k);
        }
        else{
            int x,y;
            cin>>x>>y;
            cout<<query(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}

Ex.

CF339D

线段树1.5（大内存动态开点）

#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
struct node{
    int ls = 0;
    int rs = 0;
    ull sum = 0;
    ull lazy = 0;
};
vector<node> tree(1);
int newNode(){
    tree.push_back(node());
    return tree.size()-1;
}
void pushup(int p){
    tree[p].sum = tree[tree[p].ls].sum + tree[tree[p].rs].sum;
    return;
}
void pushdown(int p, ll l, ll r){
    if(tree[p].lazy == 0){
        return;
    }
    ll mid = (l+r) >> 1;
    if(tree[p].ls == 0){
        int x = newNode();
        tree[p].ls = x;
    }
    if(tree[p].rs == 0){
        int x = newNode();
        tree[p].rs = x;
    }
    int ls = tree[p].ls, rs = tree[p].rs;
    ull tag = tree[p].lazy;
    tree[ls].sum += 1ULL * (mid - l + 1)*tree[p].lazy;
    tree[rs].sum += 1ULL*(r - mid)*tree[p].lazy;
    tree[ls].lazy += tag;
    tree[rs].lazy += tag;
    tree[p].lazy = 0;
}
int modify(int p, ll l, ll r, ll ql, ll qr, ull k){//当前节点编号，节点掌控的区间，目标修改区间，增加的幅度
    if(p == 0){
        p = newNode();
    }
    if(ql <= l && qr >= r){
        tree[p].lazy += k;
        tree[p].sum += 1ULL*(r - l + 1)*k;
        return p;
    }
    pushdown(p, l, r);
    ll mid = (l + r) >> 1;
    if(ql <= mid){
        int m =modify(tree[p].ls, l, mid,ql, qr, k);
        tree[p].ls = m;
    }
    if(qr > mid){
        int m = modify(tree[p].rs, mid + 1, r, ql, qr, k);
        tree[p].rs = m;
    }
    pushup(p);
    return p;
}
ull query(int p, ll l, ll r, ll ql, ll qr){
    if (p == 0)
        return 0;

    if (ql <= l && r <= qr)
        return tree[p].sum;

    pushdown(p, l, r);

    long long mid = (l + r) >> 1;

    unsigned long long ans = 0;

    if (ql <= mid)
        ans += query(tree[p].ls, l, mid, ql, qr);

    if (qr > mid)
        ans += query(tree[p].rs, mid + 1, r, ql, qr);

    return ans;
}
int main(){
    int n,m;
    cin >> n >> m;
    int root = 0;
    while(m--){
        int op;
        
        cin >> op;

        if (op == 1) {
            ll l, r;
            ull k;

            cin >> l >> r >> k;
            root = modify(root, 1, n, l, r, k);
        }

        else {
            ll l, r;

            cin >> l >> r;
            ull original =(1ULL * l + r) * (r - l + 1)/ 2;
            cout <<query(root, 1, n, l, r) + original<<endl;
            
        }
    }
    
    return 0;
}

线段树2（+，x双维护）

由于线段树本质相当于将一个加和拆分到不同的小区间，分别进行运算（并且允许没有子节点

所以要求维护的运算满足结合律和存在零元

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

long long m;
long long a[100005];
long long tree[400005];
long long lazy[400005];
long long mul[400005];

// 建树
void build(int node, int l, int r) {
    mul[node] = 1;

    if (l == r) {
        tree[node] = a[l] % m;
        return;
    }

    int mid = (l + r) / 2;

    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);

    tree[node] =
        (tree[node * 2] + tree[node * 2 + 1]) % m;
}

// 对当前节点代表的整个区间乘 k
void multi(int node, long long k) {
    k %= m;

    tree[node] = tree[node] * k % m;

    mul[node] = mul[node] * k % m;
    lazy[node] = lazy[node] * k % m;
}

// 对当前节点代表的整个区间加 k
void add(int node, long long k, int l, int r) {
    k %= m;

    tree[node] =
        (tree[node] + k * (r - l + 1)) % m;

    lazy[node] =
        (lazy[node] + k) % m;
}

// 下传 lazy tag
void down(int node, int l, int r) {
    if (lazy[node] == 0 && mul[node] == 1) {
        return;
    }

    int mid = (l + r) / 2;

    // 先乘
    multi(node * 2, mul[node]);
    multi(node * 2 + 1, mul[node]);

    // 再加
    add(node * 2, lazy[node], l, mid);
    add(node * 2 + 1, lazy[node], mid + 1, r);

    // 清空当前节点的 lazy tag
    mul[node] = 1;
    lazy[node] = 0;
}

// 区间乘 k
void update_mul(
    int node,
    int l,
    int r,
    int ql,
    int qr,
    long long k
) {
    // 当前区间完全包含于修改区间
    if (ql <= l && r <= qr) {
        multi(node, k);
        return;
    }

    down(node, l, r);

    int mid = (l + r) / 2;

    if (ql <= mid) {
        update_mul(
            node * 2,
            l,
            mid,
            ql,
            qr,
            k
        );
    }

    if (qr > mid) {
        update_mul(
            node * 2 + 1,
            mid + 1,
            r,
            ql,
            qr,
            k
        );
    }

    tree[node] =
        (tree[node * 2] + tree[node * 2 + 1]) % m;
}

// 区间加 k
void update_add(
    int node,
    int l,
    int r,
    int ql,
    int qr,
    long long k
) {
    // 当前区间完全包含于修改区间
    if (ql <= l && r <= qr) {
        add(node, k, l, r);
        return;
    }

    down(node, l, r);

    int mid = (l + r) / 2;

    if (ql <= mid) {
        update_add(
            node * 2,
            l,
            mid,
            ql,
            qr,
            k
        );
    }

    if (qr > mid) {
        update_add(
            node * 2 + 1,
            mid + 1,
            r,
            ql,
            qr,
            k
        );
    }

    tree[node] =
        (tree[node * 2] + tree[node * 2 + 1]) % m;
}

// 查询区间和
long long query(
    int node,
    int l,
    int r,
    int ql,
    int qr
) {
    // 当前区间完全包含于查询区间
    if (ql <= l && r <= qr) {
        return tree[node];
    }

    down(node, l, r);

    int mid = (l + r) / 2;
    long long ans = 0;

    if (ql <= mid) {
        ans += query(
            node * 2,
            l,
            mid,
            ql,
            qr
        );

        ans %= m;
    }

    if (qr > mid) {
        ans += query(
            node * 2 + 1,
            mid + 1,
            r,
            ql,
            qr
        );

        ans %= m;
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;

    cin >> n >> q >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build(1, 1, n);

    while (q--) {

        int t;
        int x, y;
        long long k;

        cin >> t;

        // 区间乘
        if (t == 1) {

            cin >> x >> y >> k;

            update_mul(
                1,
                1,
                n,
                x,
                y,
                k
            );
        }

        // 区间加
        else if (t == 2) {

            cin >> x >> y >> k;

            update_add(
                1,
                1,
                n,
                x,
                y,
                k
            );
        }

        // 查询
        else {

            cin >> x >> y;

            cout << query(
                1,
                1,
                n,
                x,
                y
            ) << '\n';
        }
    }

    return 0;
}

用SG定理解释Nim游戏

评论