线段树基础写法

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
int n, m;
int a[MAXN + 5];
// 线段树：单点修改、区间查询（区间和）
int t[4 * MAXN + 5], lazy[4 * MAXN + 5];
// 基于a[]建线段树
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;
    // 左子树 now*2,l,mid
    // 右子树 now*2+1,mid+1,r
    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;
}
// 当前做到了树上的now号节点，当前节点对应的区间为 [l,r]
// 需要给 [x,y] 这些数都加 z
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;
    // 左子树 now*2,l,mid
    // 右子树 now*2+1,mid+1,r
    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)
{
    //[l,r] 是 [x,y] 的子区间
    if (x <= l && r <= y)
        return t[now];
    int mid = (l + r) / 2;
    // 左子树 now*2,l,mid
    // 右子树 now*2+1,mid+1,r
    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 sum(a[x]~a[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;
int a[MAXN + 5];
// 线段树：单点修改、区间查询（区间和）
int t[4 * MAXN + 5], lazy[4 * MAXN + 5];
// 基于a[]建线段树
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];
}
// 当前做到了树上的now号节点，当前节点对应的区间为 [l,r]
// 需要给 [x,y] 这些数都加 z
void update(int now, int l, int r, int x, int y, int z)
{
    t[now] += (min(y, r) - max(x, l) + 1) * z;
    if (x <= l && r <= y)
    {
        lazy[now] += z;
        return;
    }
    int mid = (l + r) / 2;
    // 左子树 now*2,l,mid
    // 右子树 now*2+1,mid+1,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);
}
int query(int now, int l, int r, int x, int y, int lazySum)
{
    //[l,r] 是 [x,y] 的子区间
    if (x <= l && r <= y)
        return t[now] + (r - l + 1) * lazySum;
    int mid = (l + r) / 2;
    // 左子树 now*2,l,mid
    // 右子树 now*2+1,mid+1,r
    int res = 0;
    lazySum += lazy[now];
    if (x <= mid)
        res += query(now * 2, l, mid, x, y, lazySum);
    if (y > mid)
        res += query(now * 2 + 1, mid + 1, r, x, y, lazySum);
    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 sum(a[x]~a[y])
            cout << query(1, 1, n, x, y, 0) << "\n";
        }
    }
    return 0;
}

树状数组写法

$d_i$ 为原数组的差分数组，则 $a_i=\sum_{j=1}^i{d_j}$

那么对应的前缀和 $sum_i=\sum_{j=1}^i{a_j} = \sum_{j=1}^i\sum_{k=1}^j{d_k}$

考虑每个 $d_k$ 的贡献易得

$sum_i = \sum_{k=1}^i{d_k\times (i-k+1)} = \sum_{k=1}^i{d_k\times (i+1)-d_k\times k} $

整理可得 $sum_i = ((i+1)\times \sum_{k=1}^i{d_k}) - \sum_{k=1}^i{d_k\times k}$

因此用两个树状数组分别维护差分数组 $d_i$ 与 $d_i\times i$ 即可。

前半部分，两个树状数组

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 500000;
int n, m;
int a[MAXN + 5];
int lowbit(int x)
{
    return x & (-x);
}
// t[] 维护差分数组 d[i]
int t[MAXN + 5];
// 第x个数加k
void update(int x, int k)
{
    for (int i = x; i <= n; i += lowbit(i))
        t[i] += k;
}
// 返回前x个数的和
int query(int x)
{
    int res = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        res += t[i];
    return res;
}
// t2[] 维护 d[i]*i
int t2[MAXN + 5];
void update2(int x, int k)
{
    for (int i = x; i <= n; i += lowbit(i))
        t2[i] += k;
}
int query2(int x)
{
    int res = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        res += t2[i];
    return res;
}

重点：求前缀和 $sum_i$

$sum_i = ((i+1)\times \sum_{k=1}^i{d_k}) - \sum_{k=1}^i{d_k\times k}$

// 利用 t[] 和 t2[] 求 a[] 的前缀和
int sum(int i)
{
    int res = 0;
    res += (i + 1) * query(i);
    res -= query2(i);
    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];
        if (i == 1)
        {
            update(i, a[i]);
            update2(i, a[i] * i);
        }
        else
        {
            update(i, a[i] - a[i - 1]);
            update2(i, (a[i] - a[i - 1]) * i);
        }
    }
    while (m--)
    {
        int op, x, y, k;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y >> k; // a[x]~a[y] +=y
            update(x, k);
            update(y + 1, -k);
            update2(x, k * x);
            update2(y + 1, -k * (y + 1));
        }
        else
        {
            cin >> x >> y; // cout sum(a[x]~a[y])
            cout << sum(y) - sum(x - 1) << "\n";
        }
    }
    return 0;
}