zl程序教程

您现在的位置是:首页 >  其他

当前栏目

P3372 【模板】线段树 1

模板 线段
2023-09-27 14:28:12 时间

题目传送门

一、使用树状数组实现

区间修改和区间查询

我们还是利用差分,可以得:
\(\displaystyle \sum_{i=1}^na_i = \sum_{i=1}^n \sum_{j=1}^i b_j\)
\(\displaystyle \ \ \ \ \ \ \ \ \ \ \ = n \times b_1 + (n-1) \times b_2 + ... + b_n\)
\(\displaystyle \ \ \ \ \ \ \ \ \ \ \ = n \times \sum_{i=1}^n b_i - \sum_{i=1}^nb_i \times (i-1)\)

方法就显而易见了:维护两个树状数组,一个维护 \(\displaystyle \sum_{i=1}^nb_i\),一个维护\(\displaystyle \sum_{i=1}^nb_i \times (i-1)\)

实现代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & -x)
typedef long long LL;
#define N 1000010
LL n, q, op, l, r, x;
LL a[N];
LL t1[N], t2[N];

LL add(LL x, LL y) {
    for (LL i = x; i <= n; i += lowbit(i)) {
        t1[i] += y;
        t2[i] += x * y;
    }
}

LL ask(LL x) {
    LL ans = 0;
    for (LL i = x; i; i -= lowbit(i)) ans += (x + 1) * t1[i] - t2[i];
    return ans;
}

int main() {
    scanf("%lld%lld", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        add(i, a[i] - a[i - 1]);
    }
    for (int i = 1; i <= q; i++) {
        scanf("%d%lld%lld", &op, &l, &r);
        if (op == 1) {
            scanf("%lld", &x);
            add(l, x);
            add(r + 1, -x);
        } else
            printf("%lld\n", ask(r) - ask(l - 1));
    }
    return 0;
}

二、使用线段树实现