线段树

2024-08-11

通过建立线段树的数据结构,添加Lazy-Tag,实现区间修改和区间查询的操作

#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 100015;
int a[N], tree[N << 2], tag[N << 2], ma[N << 2];
void push_up(int p)
{
    tree[p] = tree[p << 1] + tree[p << 1 | 1];
    ma[p] = max(ma[p << 1], ma[p << 1 | 1]);
}
void build(int p, int pl, int pr)
{
    tag[p] = 0;
    if (pl == pr)
    {
        tree[p] = a[pl];
        ma[p] = a[pl];
        return;
    }
    int mid = (pl + pr) >> 1;
    build(p << 1, pl, mid);
    build(p << 1 | 1, mid + 1, pr);
    push_up(p);
}
void addtag(int p, int pl, int pr, int d)
{
    tag[p] += d;
    tree[p] += d * (pr - pl + 1);
    ma[p] += d;
}
void push_down(int p, int pl, int pr)
{
    if (tag[p])
    {
        int mid = (pl + pr) >> 1;
        addtag(p << 1, pl, mid, tag[p]);
        addtag(p << 1 | 1, mid + 1, pr, tag[p]);
        tag[p] = 0;
    }
}
void update(int l, int r, int p, int pl, int pr, int d)
{
    if (l <= pl && pr <= r)
    {
        addtag(p, pl, pr, d);
        return;
    }
    push_down(p, pl, pr);
    int mid = (pl + pr) >> 1;
    if (l <= mid)
        update(l, r, p << 1, pl, mid, d);
    if (r > mid)
        update(l, r, p << 1 | 1, mid + 1, pr, d);
    push_up(p);
}
int querySum(int l, int r, int p, int pl, int pr)
{
    if (pl >= l && r >= pr)
        return tree[p];
    push_down(p, pl, pr);
    int res = 0;
    int mid = (pl + pr) >> 1;
    if (l <= mid)
        res += querySum(l, r, p << 1, pl, mid);
    if (r > mid)
        res += querySum(l, r, p << 1 | 1, mid + 1, pr);
    return res;
}
int queryMax(int l, int r, int p, int pl, int pr)
{
    if (pl >= l && r >= pr)
        return ma[p];
    push_down(p, pl, pr);
    int res = SUB;
    int mid = (pl + pr) >> 1;
    if (l <= mid)
        res = max(res, queryMax(l, r, p << 1, pl, mid));
    if (r > mid)
        res = max(res, queryMax(l, r, p << 1 | 1, mid + 1, pr));
    return res;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    while (m--)
    {
        int q, l, r, d;
        scanf("%d", &q);
        if (q == 0)
        {
            scanf("%d%d%d", &l, &r, &d);
            update(l, r, 1, 1, n, d);
        }
        else if (q == 1)
        {
            scanf("%d%d", &l, &r);
            printf("%d\n", queryMax(l, r, 1, 1, n));
        }
        else if (q == 2)
        {
            scanf("%d%d", &l, &r);
            printf("%d\n", querySum(l, r, 1, 1, n));
        }
    }
    return 0;
}