树状数组

洛谷 P3374 【模板】树状数组 1

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const int maxn(5e5 + 10);
int c[maxn];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, bool ln)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (ln) putchar(10);
}

inline int lowbit(int x)
{
    return x & -x;
}

void update(int p, int n, int v)
{
    for (int i = p; i <= n; i += lowbit(i)) {
        c[i] += v;
    }
}

ll getSum(int p)
{
    ll sum = 0;
    while (p) {
        sum += c[p];
        p -= lowbit(p);
    }
    return sum;
}

ll query(int l, int r)
{
    return getSum(r) - getSum(l - 1);
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        update(i, n, read());
    }
    while (m--) {
        int op = read(), a = read(), b = read();
        if (op == 1) {
            update(a, n, b);
        } else {
            write(query(a, b), true);
        }
    }
    return 0;
}

洛谷 P3368 【模板】树状数组 2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const int maxn(5e5 + 10);
int c[maxn];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, bool ln)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (ln) putchar(10);
}

inline int lowbit(int x)
{
    return x & -x;
}

void update(int p, int n, int v)
{
    for (int i = p; i <= n; i += lowbit(i)) {
        c[i] += v;
    }
}

ll getSum(int p)
{
    ll sum = 0;
    while (p) {
        sum += c[p];
        p -= lowbit(p);
    }
    return sum;
}

ll query(int l, int r)
{
    return getSum(r) - getSum(l - 1);
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        update(i, n, read());
    }
    while (m--) {
        int op = read(), a = read(), b = read();
        if (op == 1) {
            update(a, n, b);
        } else {
            write(query(a, b), true);
        }
    }
    return 0;
}

洛谷 P3372 【模板】线段树 1

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const int maxn(1e5 + 10);
int a[maxn];
ll c[maxn][2];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, bool ln)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (ln) putchar(10);
}

inline int lowbit(int x)
{
    return x & -x;
}

void add(int t, int p, int n, ll v)
{
    for (int i = p; i <= n; i += lowbit(i)) {
        c[i][t] += v;
    }
}

ll getSum(int t, int p)
{
    ll sum = 0;
    for (int i = p; i; i -= lowbit(i)) {
        sum += c[i][t];
    }
    return sum;
}

void update(int l, int r, int n, int v)
{
    add(0, l, n, v);
    add(0, r + 1, n, -v);
    add(1, l, n, 1ll * v * (l - 1));
    add(1, r + 1, n, -1ll * v * r);
}

ll query(int l, int r)
{
    ll sum_r = 1ll * r * getSum(0, r) - getSum(1, r);
    ll sum_l = 1ll * (l - 1) * getSum(0, l - 1) - getSum(1, l - 1);
    return sum_r - sum_l;
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        add(0, i, n, a[i] - a[i - 1]);
        add(1, i, n, 1ll * (a[i] - a[i - 1]) * (i - 1));
    }
    while (m--) {
        int op = read(), x = read(), y = read();
        if (op == 1) {
            int k = read();
            update(x, y, n, k);
        } else {
            write(query(x, y), true);
        }
    }
    return 0;
}