线段树

简介

线段树是算法竞赛中用来维护区间性质最常用的数据结构。
可以在 的时间内达成区间修改，区间查询，单点修改，解决区间最大最小值(RMQ)问题。
但是要注意一点：线段树维护的信息，需要满足可加性，即能以可以接受的速度合并信息和修改信息，包括在使用懒惰标记时，标记也要满足可加性（例如取模就不满足可加性，对 6 取模然后对 7 取模，两个操作就不能合并在一起做）。
线段树需要开 n * 4 的空间消耗。
下方代码为了存在更好的可读性，省略代码头文件与其他无关的函数。

P3372 【模板】线段树 1

裸的模板题了，需要熟练掌握推标记的操作

const int N = 1e5 + 7;

#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
ll a[N], sum[N << 2], lazy[N << 2];

void build(int rt, int l, int r) {
    if (l == r) {
        sum[rt] = a[l];
        lazy[rt] = 0;
        return;
    }
    build(lson);
    build(rson);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void push_down(int rt, int l, int r) {
    if (lazy[rt]) {
        sum[rt << 1] += lazy[rt] * (mid - l + 1);
        sum[rt << 1 | 1] += lazy[rt] * (r - mid);
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
    }
}
void update(int rt, int l, int r, int L, int R, ll z) {
    if (L <= l and r <= R) {
        sum[rt] += z * (r - l + 1);
        lazy[rt] += z;
        return;
    }
    push_down(rt, l, r);
    if (L <= mid)    update(lson, L, R, z);
    if (R > mid)    update(rson, L, R, z);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
ll query(int rt, int l, int r, int L, int R) {
    if (L <= l and r <= R)    return sum[rt];
    push_down(rt, l, r);
    ll res = 0;
    if (L <= mid)    res += query(lson, L, R);
    if (R > mid)    res += query(rson, L, R);
    return res;
}

int main() {
    int T = 1;
    //T = read();
    while (T--) {
        int n = read(), m = read();
        for (int i = 1; i <= n; ++i)    a[i] = read();
        build(1, 1, n);
        while (m--) {
            int op = read();
            if (op & 1) {
                int x = read(), y = read(), z = read();
                update(1, 1, n, x, y, z);
            }
            else {
                int x = read(), y = read();
                print(query(1, 1, n, x, y));
            }
        }
    }
    return 0;
}

P3373 【模板】线段树 2

加法标记，乘法标记，注意乘法标记优先级比加法优先级更高哦。
与上方类似推动标记即可。

const int N = 1e5 + 7;

#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
ll a[N], sum[N << 2], lazy[N << 2], mul[N << 2];
ll mod;

void push_up(int rt) { sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % mod; }
void push_down(int rt, int l, int r) {
    if (mul[rt] != 1) {
        mul[rt << 1] = (mul[rt << 1] * mul[rt]) % mod;
        mul[rt << 1 | 1] = (mul[rt << 1 | 1] * mul[rt]) % mod;
        lazy[rt << 1] = (lazy[rt << 1] * mul[rt]) % mod;
        lazy[rt << 1 | 1] = (lazy[rt << 1 | 1] * mul[rt]) % mod;
        sum[rt << 1] = (sum[rt << 1] * mul[rt]) % mod;
        sum[rt << 1 | 1] = (sum[rt << 1 | 1] * mul[rt]) % mod;
        mul[rt] = 1;
    }
    if (lazy[rt]) {
        sum[rt << 1] = (sum[rt << 1] + lazy[rt] * (mid - l + 1)) % mod;
        sum[rt << 1 | 1] = (sum[rt << 1 | 1] + lazy[rt] * (r - mid)) % mod;
        lazy[rt << 1] = (lazy[rt << 1] + lazy[rt]) % mod;
        lazy[rt << 1 | 1] = (lazy[rt << 1 | 1] + lazy[rt]) % mod;
        lazy[rt] = 0;
    }
}
void build(int rt, int l, int r) {
    mul[rt] = 1;
    if (l == r) {
        sum[rt] = a[l];
        return;
    }
    build(lson);
    build(rson);
    push_up(rt);
}
void update1(int rt, int l, int r, int L, int R, ll z) { // 乘法
    if (L <= l and r <= R) {
        mul[rt] = mul[rt] * z % mod;
        lazy[rt] = lazy[rt] * z % mod;
        sum[rt] = sum[rt] * z % mod;
        return;
    }
    push_down(rt, l, r);
    if (L <= mid)    update1(lson, L, R, z);
    if (R > mid)    update1(rson, L, R, z);
    push_up(rt);
}
void update2(int rt, int l, int r, int L, int R, ll z) { // 加法
    if (L <= l and r <= R) {
        sum[rt] = (sum[rt] + z * (r - l + 1)) % mod;
        lazy[rt] = (lazy[rt] + z) % mod;
        return;
    }
    push_down(rt, l, r);
    if (L <= mid)    update2(lson, L, R, z);
    if (R > mid)    update2(rson, L, R, z);
    push_up(rt);
}
ll query(int rt, int l, int r, int L, int R) {
    if (L <= l and r <= R)    return sum[rt];
    push_down(rt, l, r);
    ll res = 0;
    if (L <= mid)    res += query(lson, L, R);
    res %= mod;
    if (R > mid)    res += query(rson, L, R);
    return res % mod;
}

int main() {
    int T = 1;
    //T = read();
    while (T--) {
        int n = read(), m = read();
        mod = read();
        for (int i = 1; i <= n; ++i)    a[i] = read();
        build(1, 1, n);
        while (m--) {
            int op = read();
            if (op == 1) {
                int x = read(), y = read(), z = read();
                update1(1, 1, n, x, y, z);
            }
            else if (op == 2) {
                int x = read(), y = read(), z = read();
                update2(1, 1, n, x, y, z);
            }
            else {
                int x = read(), y = read();
                print(query(1, 1, n, x, y));
            }
        }
    }
    return 0;
}

线段树的区间修改

有关区间赋值运算的区间修改

const int N = 1e5 + 7;

#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
ll a[N], sum[N << 2], assign[N << 2];

void push_up(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }
void push_down(int rt, int l, int r) {
    if (assign[rt]) {
        sum[rt << 1] = assign[rt] * (mid - l + 1);
        sum[rt << 1 | 1] = assign[rt] * (r - mid);
        assign[rt << 1] = assign[rt << 1 | 1] = assign[rt];
        assign[rt] = 0;
    }
}
void build(int rt, int l, int r) {
    if (l == r) {
        sum[rt] = a[l];
        return;
    }
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int rt, int l, int r, int L, int R, ll z) {
    if (L <= l and r <= R) {
        sum[rt] = z * (r - l + 1);
        assign[rt] = z;
        return;
    }
    push_down(rt, l, r);
    if (L <= mid)    update(lson, L, R, z);
    if (R > mid)    update(rson, L, R, z);
    push_up(rt);
}
ll query(int rt, int l, int r, int L, int R) {
    if (L <= l and r <= R)    return sum[rt];
    push_down(rt, l, r);
    ll res = 0;
    if (L <= mid)    res += query(lson, L, R);
    if (R > mid)    res += query(rson, L, R);
    return res;
}

int main() {
    int T = 1;
    //T = read();
    while (T--) {
        int n = read();
        for (int i = 1; i <= n; ++i)    a[i] = read();
        build(1, 1, n);
        int m = read();
        while (m--) {
            int op = read();
            if (op == 0) {
                int x = read(), y = read();
                ll ans = query(1, 1, n, x, y);
                print(ans);
            }
            else {
                int x = read(), y = read(), z = read();
                update(1, 1, n, x, y, z);
            }
        }
    }
    return 0;
}

求最大值

首先观察需要求解的式子，如果把 看成横坐标，看成纵坐标，那么所求的就是任意两点间最大的斜率。
那么画图观察之后，你会发现，这个斜率的最大值一定是在相邻的点中出现的。
我们使用反证法证明，可以假设，如果存在一对点斜率最大但是不是相邻的。那么也就是中间一定还存在最少一个点。这个点要么发布在之前两点的连线上方要么出现在下方，但是无论上方还是下方，由起点和中间点，或者中间点和终点的斜率都会大于起始斜率，这与我们的假设相矛盾。所以假设不成立。
那么我们就把问题转换成了求一个最大的差分数组。
最后处理一下最后一个点的情况就行了。因为这最后一个点的修改只用该本身，不需要改后面的哪一个点。

const int N = 2e5 + 7;

int a[N], b[N << 2], n, m;
#define mid (l + r >> 1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r

void build(int rt, int l, int r) {
    if (l == r) { b[rt] = a[l] - a[l - 1]; return; }
    build(lson);
    build(rson);
    b[rt] = max(b[rt << 1], b[rt << 1 | 1]);
}

void update(int rt, int l, int r, int idx, int val) {
    if (l == r) { b[rt] = val; return; }
    if (idx <= mid)    update(lson, idx, val);
    else update(rson, idx, val);
    b[rt] = max(b[rt << 1], b[rt << 1 | 1]);
}

void solve() {
    rep(i, 1, n)    a[i] = read();
    build(1, 2, n);
    m = read();
    while (m--) {
        int idx = read(), val = read();
        a[idx] = val;
        update(1, 2, n, idx, a[idx] - a[idx - 1]);
        if (idx < n)    update(1, 2, n, idx + 1, a[idx + 1] - a[idx]);
        printf("%d.00\n", b[1]);
    }
}

签到题

观察给出的代码，发现需要我们模拟查找的就是从 1 到 L 一共有几个点被赋值为 1。
跟着它代码的思路遍历容器是会TLE的，如果数据不水的话，这个题目好像可以混过去。
但是正解就是类似线段树的做法。
使用一个懒惰标记，标识区间中全部中最小的覆盖次数。
那么每次查询的时候如果当前标记大于0，直接累加区间长度即可。
注意和的写法就行了。

const int N = 1e5 + 7;

#define mid (r+l >> 1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid + 1, r
int cover[N << 2], n, m;

void push_down(int rt) {
    if (cover[rt]) {
        cover[rt << 1] += cover[rt];
        cover[rt << 1 | 1] += cover[rt];
        cover[rt] = 0;
    }
}

void push_up(int rt) {
    int z = min(cover[rt << 1], cover[rt << 1 | 1]);
    cover[rt] += z;
    cover[rt << 1] -= z;
    cover[rt << 1 | 1] -= z;
}

void update(int rt, int l, int r, int L, int R, int z) {
    if (l >= L and r <= R) {
        cover[rt] += z;
        return;
    }
    push_down(rt);
    if (L <= mid)    update(lson, L, R, z);
    if (R > mid) update(rson, L, R, z);
    push_up(rt);
}

int query(int rt, int l, int r, int L, int R) {
    int res = 0;
    if (cover[rt] > 0)
        res += r - l + 1;
    else if (l != r) {
        push_down(rt);
        res += query(lson, L, R);
        res += query(rson, L, R);
        push_up(rt);
    }
    return res;
}

void solve() {
    set<pai> st;
    m = read(), n = read();
    while (m--) {
        int op = read(), l = read(), r = read();
        if (op == 1) {
            if (st.find({ l,r }) != st.end())    continue;
            st.insert({ l,r });
            update(1, 1, n, l, r, 1);
        }
        else if (op == 2) {
            if (st.find({ l,r }) == st.end())    continue;
            st.erase({ l,r });
            update(1, 1, n, l, r, -1);
        }
        else print(query(1, 1, n, 1, n));
    }
}

小阳的贝壳

首先有关的一个前缀知识，更相减陨法，简单证明一下。
如果对于两个数的最大公因数是，那么也就是可以表示为，那么也能被整除。
所以如果我们得到，当然这个式子是不能通过更相减陨法求解出来的因为它只有在保证才能迭代出正确结果。
但是使用辗转相除法求解就不用那么大的顾虑了。这个地方比较妙！使用更相减陨法证明两个式子相同，再使用辗转相除法求解答案。
那么再看这个题目，一个是区间全部加上一个数，可以使用差分处理。
一个里面的最大的差分值。还有一个求区间里面最大的，那么我们根据更相减陨法看下面的一段式子。
首先得到的差分数组，因为后续不需要用到原数组了，所以可以直接在数组上改变。 使用线段树维护这个差分数组左端点加一个数，因为是线段树维护所以需要判断右端点加一是否越界，如果不越界就把右端点减掉一个数。
我们可以通过一个标记通过前缀和求出的值，接下来，如果你要查询的是的时候，注意特判
其余时候去判断的最大值即可，在使用一个新的标记统计各个节点的，依次递归回到顶部就会拿到最大的区间
到了的时候，在存储叶子节点的的时候，如果存储的就是当前节点的，那么通过上方推出的关系式。先拿到的值。
再去求道的绝对值差分数组最大的，同理实现方法也是使用一个新的标记去计算，最后再求解一下就是答案了。也是要注意特判一下区间长度比较好。
下面给出代码。

const int N = 1e5 + 7;

#define mid (l+r>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
int a[N], sum[N << 2], g[N << 2], maxi[N << 2];
int n, m;

void push_up(int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    g[rt] = gcd(g[rt << 1], g[rt << 1 | 1]);
    maxi[rt] = max(maxi[rt << 1], maxi[rt << 1 | 1]);
}

void build(int rt, int l, int r) {
    if (l == r) {
        sum[rt] = a[l];
        maxi[rt] = abs(sum[rt]);
        g[rt] = maxi[rt];
        return;
    }
    build(lson);
    build(rson);
    push_up(rt);
}

void update(int rt, int l, int r, int L, int val) {
    if (l == r) {
        a[L] += val;
        sum[rt] = a[l];
        maxi[rt] = abs(sum[rt]);
        g[rt] = maxi[rt];
        return;
    }
    if (L <= mid)    update(lson, L, val);
    else update(rson, L, val);
    push_up(rt);
}

int query_sum(int rt, int l, int r, int L, int R) {
    if (L <= l and r <= R)    return sum[rt];
    int res = 0;
    if (L <= mid)    res += query_sum(lson, L, R);
    if (R > mid)    res += query_sum(rson, L, R);
    return res;
}

int query_max(int rt, int l, int r, int L, int R) {
    if (L <= l and r <= R)    return maxi[rt];
    int res = 0;
    if (L <= mid)    res = max(res, query_max(lson, L, R));
    if (R > mid)    res = max(res, query_max(rson, L, R));
    return res;
}

int query_gcd(int rt, int l, int r, int L, int R) {
    if (L <= l and r <= R)    return g[rt];
    int res = 0;
    if (L <= mid)    res = gcd(res, query_gcd(lson, L, R));
    if (R > mid)    res = gcd(res, query_gcd(rson, L, R));
    return res;
}

void solve() {
    n = read(), m = read();
    rep(i, 1, n)    a[i] = read();
    for (int i = n; i; --i)    a[i] -= a[i - 1];
    build(1, 1, n);
    while (m--) {
        int op = read(), l = read(), r = read();
        if (op == 1) {
            int x = read();
            update(1, 1, n, l, x);
            if (r < n)    update(1, 1, n, r + 1, -x);
        }
        else if (op == 2) {
            if (l == r)    puts("0");
            else {
                int ans = query_max(1, 1, n, l + 1, r);
                print(ans);
            }
        }
        else {
            int ans;
            if (l == r)    ans = query_sum(1, 1, n, 1, l);
            else ans = gcd(query_sum(1, 1, n, 1, l), query_gcd(1, 1, n, l + 1, r));
            print(ans);
        }
    }
}

区区区间

长度为的序列，有次操作，每次可以查询一段区间的和，也可以修改一段区间的值为
线段数推标记，使用一个标记暂缓赋值操作，记录的是当前管理区间的赋值。那么一个的等差数列也可以很好算出来。
管理好推标记的方案就行了。

const int N = 2e5 + 7;

#define mid ( l+r >> 1 )
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r

int a[N], n, m;
ll sum[N << 2], lazy[N << 2];

ll calc(ll a1, ll n) {
    return (a1 + a1 + n - 1) * n / 2;
}
void push_up(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }
void push_down(int rt, int l, int r) {
    if (lazy[rt]) {
        lazy[rt << 1] = lazy[rt];
        lazy[rt << 1 | 1] = lazy[rt] + (mid - l + 1);
        sum[rt << 1] = calc(lazy[rt << 1], mid - l + 1);
        sum[rt << 1 | 1] = calc(lazy[rt << 1 | 1], r - mid);
        lazy[rt] = 0;
    }
}

void build(int rt, int l, int r) {
    if (l == r) {
        sum[rt] = a[l];
        return;
    }
    build(lson);
    build(rson);
    push_up(rt);
}

void update(int rt, int l, int r, int L, int R, int k) {
    if (L <= l and r <= R) {
        ll a1 = k + l - L, n = r - l + 1;
        lazy[rt] = a1;
        sum[rt] = calc(a1, n);
        return;
    }
    push_down(rt, l, r);
    if (L <= mid)    update(lson, L, R, k);
    if (R > mid)    update(rson, L, R, k);
    push_up(rt);
}

ll query(int rt, int l, int r, int L, int R) {
    if (L <= l and r <= R)    return sum[rt];
    push_down(rt, l, r);
    ll res = 0;
    if (L <= mid)    res += query(lson, L, R);
    if (R > mid)    res += query(rson, L, R);
    return res;
}

void solve() {
    n = read(), m = read();
    rep(i, 1, n)    a[i] = read();
    build(1, 1, n);
    while (m--) {
        int op = read(), l = read(), r = read();
        if (op & 1) {
            int k = read();
            update(1, 1, n, l, r, k);
        }
        else {
            ll ans = query(1, 1, n, l, r);
            print(ans);
        }
    }
}

小翔和泰拉瑞亚

给出长度为的起始序列，权值代表高度，后面有次操作，使得区间高度减少，现在需要你选取一些操作求修改后的序列最大的高度差值是多少？选择的操作数可以为0。
首先观察这个修改操作，显然如果选取了某次操作，我们是可以通过线段数去很容易的维护区间的最大值和最小值。那么最大差值也很容易计算。
现在有一个点困难的是，我们如何挑配一定的操作序列？不需要去挑取，只需要在差分的时候保留最大值即可。
我们离线全部的修改序列操作，并且记录每次减少高度和回归高度是在那些操作会进行，有个小技巧使用正负两种数记录操作数就可以区分是把高度调高还是调低了。
记录完毕之后，从枚举到去看看当前的差分处理之后会不会影响最终答案。

const int N = 2e5 + 7;

#define mid ( l+r >> 1 )
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r

int a[N], n, m;
ll maxi[N << 2], mini[N << 2], lazy[N << 2];

void push_up(int rt) {
    maxi[rt] = max(maxi[rt << 1], maxi[rt << 1 | 1]);
    mini[rt] = min(mini[rt << 1], mini[rt << 1 | 1]);
}
void push_down(int rt) {
    if (lazy[rt]) {
        maxi[rt << 1] += lazy[rt];
        mini[rt << 1] += lazy[rt];
        maxi[rt << 1 | 1] += lazy[rt];
        mini[rt << 1 | 1] += lazy[rt];
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
    }
}

void build(int rt, int l, int r) {
    if (l == r) {
        maxi[rt] = mini[rt] = a[l];
        return;
    }
    build(lson);
    build(rson);
    push_up(rt);
}

void update(int rt, int l, int r, int L, int R, int k) {
    if (L <= l and r <= R) {
        maxi[rt] += k;
        mini[rt] += k;
        lazy[rt] += k;
        return;
    }
    push_down(rt);
    if (L <= mid)    update(lson, L, R, k);
    if (R > mid)    update(rson, L, R, k);
    push_up(rt);
}

vector<int> p[N];
int l[N], r[N], w[N];

void solve() {
    n = read(), m = read();
    rep(i, 1, n)    a[i] = read();
    build(1, 1, n);
    rep(i, 1, m) {
        l[i] = read(), r[i] = read(), w[i] = read();
        p[l[i]].push_back(i);
        p[r[i] + 1].push_back(-i);
    }
    ll ans = maxi[1] - mini[1];
    rep(i, 1, n) { // 遍历差分列
        for (auto& it : p[i]) {
            if (it > 0)    update(1, 1, n, l[it], r[it], -w[it]); // 存在一个对pos_i的操作使得这个区间内全部数-1
            else update(1, 1, n, l[-it], r[-it], w[-it]); // 存在一个pos_i的操作与之前-1操作对应现在离开这个区间了我需要把高度回调
        }
        ans = max(ans, maxi[1] - mini[1]);
    }
    print(ans);
}

HDU4027、Can you answer these queries?

给你一个长度为的起始序列，保证序列的总和小于，现在你有次询问或者操作。
要么把一个区间内的数都变成。
要么查询的值。那么观察这个区间全部取根号的操作因为不具备可叠加的性质，所以无法使用懒惰标记加速。
但是使用计算一下一直开根号到只需要六步左右，所以当区间的和为区间长度时，无需递归了。使用这个优化即可通过本题。
其他的求合操作就是很普通的线段树操作就可以完成了。

const int N = 1e5 + 7;

#define mid ( l+r >> 1 )
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r

ll a[N], n, m;
ll sum[N << 2];

void push_up(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }

void build(int rt, int l, int r) {
    if (l == r) {
        sum[rt] = a[l];
        return;
    }
    build(lson);
    build(rson);
    push_up(rt);
}

void update(int rt, int l, int r, int L, int R) {
    if (sum[rt] == r - l + 1)    return;
    if (l == r) {
        sum[rt] = sqrt(sum[rt]);
        return;
    }
    if (L <= mid)    update(lson, L, R);
    if (R > mid)    update(rson, L, R);
    push_up(rt);
}

ll query(int rt, int l, int r, int L, int R) {
    if (L <= l and r <= R)    return sum[rt];
    ll res = 0;
    if (L <= mid)    res += query(lson, L, R);
    if (R > mid)    res += query(rson, L, R);
    return res;
}

int T = 0;
void solve() {
    printf("Case #%d:\n", ++T);
    rep(i, 1, n)    a[i] = read();
    build(1, 1, n);
    m = read();
    while (m--) {
        int op = read(), l = read(), r = read();
        if (l > r)    swap(l, r);
        if (op == 0) {
            update(1, 1, n, l, r);
        }
        else {
            ll ans = query(1, 1, n, l, r);
            print(ans);
        }
    }
    puts("");
}
int main() {
    while (~scanf("%d", &n))
        solve();
    return 0;
}

求解最大字段和