05-算法模板/02-线段树

单点修改、区间查询

【模板】树状数组 1

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int n, m;
int a[MAXN + 5];
int t[MAXN * 4 + 5];

void build(int now, int l, int r)
{
    if (l == r)
    {
        t[now] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(now * 2, l, mid);
    build(now * 2 + 1, mid + 1, r);
    t[now] = t[now * 2] + t[now * 2 + 1];
}

void update(int now, int l, int r, int x, int y)
{
    if (l == r)
    {
        t[now] += y;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
        update(now * 2, l, mid, x, y);
    if (x > mid)
        update(now * 2 + 1, mid + 1, r, x, y);
    t[now] = t[now * 2] + t[now * 2 + 1];
}

int query(int now, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
        return t[now];
    int mid = (l + r) / 2;
    int res = 0;
    if (x <= mid)
        res += query(now * 2, l, mid, x, y);
    if (y >= mid + 1)
        res += query(now * 2 + 1, mid + 1, r, x, y);
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        int op, x, y;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y;
            update(1, 1, n, x, y);
        }
        if (op == 2)
        {
            cin >> x >> y;
            cout << query(1, 1, n, x, y) << "\n";
        }
    }
    return 0;
}

区间修改、区间查询（懒标记）

【模板】线段树 1

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
int n, m;
int a[MAXN + 5];
int t[MAXN * 4 + 5], lazy[MAXN * 4 + 5];

void build(int now, int l, int r)
{
    if (l == r)
    {
        t[now] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(now * 2, l, mid);
    build(now * 2 + 1, mid + 1, r);
    t[now] = t[now * 2] + t[now * 2 + 1];
}

void down(int now, int l, int r)
{
    int mid = (l + r) / 2;
    lazy[now * 2] += lazy[now];
    t[now * 2] += (mid - l + 1) * lazy[now];
    lazy[now * 2 + 1] += lazy[now];
    t[now * 2 + 1] += (r - mid) * lazy[now];
    lazy[now] = 0;
}

void update(int now, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y)
    {
        t[now] += (r - l + 1) * z;
        lazy[now] += z;
        return;
    }
    int mid = (l + r) / 2;
    down(now, l, r);
    if (x <= mid)
        update(now * 2, l, mid, x, y, z);
    if (y > mid)
        update(now * 2 + 1, mid + 1, r, x, y, z);
    t[now] = t[now * 2] + t[now * 2 + 1];
}

int query(int now, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
        return t[now];
    int mid = (l + r) / 2;
    down(now, l, r);
    int res = 0;
    if (x <= mid)
        res += query(now * 2, l, mid, x, y);
    if (y > mid)
        res += query(now * 2 + 1, mid + 1, r, x, y);
    return res;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    while (m--)
    {
        int op, x, y, z;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y >> z;
            update(1, 1, n, x, y, z);
        }
        else
        {
            cin >> x >> y;
            cout << query(1, 1, n, x, y) << "\n";
        }
    }
    return 0;
}

区间加 + 区间乘 + 区间和查询

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
int n, m, p;
int a[MAXN + 5];
int t[MAXN * 4 + 5];
int lazyAdd[MAXN * 4 + 5], lazyMul[MAXN * 4 + 5];

void build(int now, int l, int r)
{
    lazyAdd[now] = 0;
    lazyMul[now] = 1;
    if (l == r)
    {
        t[now] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(now * 2, l, mid);
    build(now * 2 + 1, mid + 1, r);
    t[now] = (t[now * 2] + t[now * 2 + 1]) % p;
}

void down(int now, int l, int r)
{
    int mid = (l + r) / 2;
    int add = lazyAdd[now], mul = lazyMul[now];

    lazyMul[now * 2] = lazyMul[now * 2] * mul % p;
    lazyAdd[now * 2] = (lazyAdd[now * 2] * mul + add) % p;
    t[now * 2] = (t[now * 2] * mul + (mid - l + 1) * add) % p;

    lazyMul[now * 2 + 1] = lazyMul[now * 2 + 1] * mul % p;
    lazyAdd[now * 2 + 1] = (lazyAdd[now * 2 + 1] * mul + add) % p;
    t[now * 2 + 1] = (t[now * 2 + 1] * mul + (r - mid) * add) % p;

    lazyAdd[now] = 0;
    lazyMul[now] = 1;
}

void update_add(int now, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y)
    {
        t[now] = (t[now] + (r - l + 1) * z) % p;
        lazyAdd[now] = (lazyAdd[now] + z) % p;
        return;
    }
    int mid = (l + r) / 2;
    down(now, l, r);
    if (x <= mid)
        update_add(now * 2, l, mid, x, y, z);
    if (y > mid)
        update_add(now * 2 + 1, mid + 1, r, x, y, z);
    t[now] = (t[now * 2] + t[now * 2 + 1]) % p;
}

void update_mul(int now, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y)
    {
        t[now] = t[now] * z % p;
        lazyMul[now] = lazyMul[now] * z % p;
        lazyAdd[now] = lazyAdd[now] * z % p;
        return;
    }
    int mid = (l + r) / 2;
    down(now, l, r);
    if (x <= mid)
        update_mul(now * 2, l, mid, x, y, z);
    if (y > mid)
        update_mul(now * 2 + 1, mid + 1, r, x, y, z);
    t[now] = (t[now * 2] + t[now * 2 + 1]) % p;
}

int query(int now, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
        return t[now];
    int mid = (l + r) / 2;
    down(now, l, r);
    int res = 0;
    if (x <= mid)
        res = (res + query(now * 2, l, mid, x, y)) % p;
    if (y > mid)
        res = (res + query(now * 2 + 1, mid + 1, r, x, y)) % p;
    return res;
}

动态开点线段树（权值线段树）

中位数

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXAI = 1'000'000'000;
int n, a[MAXN + 5];
int tot = 1;
int lson[MAXN * 30 + 5], rson[MAXN * 30 + 5];
int t[MAXN * 30 + 5];

void update(int now, int l, int r, int x, int y)
{
    if (l == r)
    {
        t[now] += y;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
    {
        if (!lson[now])
            lson[now] = ++tot;
        update(lson[now], l, mid, x, y);
    }
    if (x > mid)
    {
        if (!rson[now])
            rson[now] = ++tot;
        update(rson[now], mid + 1, r, x, y);
    }
    t[now] = t[lson[now]] + t[rson[now]];
}

// 在线段树上二分，找第 k 小
int kth(int now, int l, int r, int k)
{
    if (l == r)
        return l;
    int mid = (l + r) / 2;
    if (t[lson[now]] >= k)
        return kth(lson[now], l, mid, k);
    return kth(rson[now], mid + 1, r, k - t[lson[now]]);
}