线段树

区间修改+区间求和 logN

const int N = 1e5 + 5;
int a[N];
namespace SEG
{
    struct tag
    {
        long long sum;
        long long lazy;
    } c[N << 2];
    void pushDown(int k, int l, int r)
    {
        int mid = (l + r) >> 1;

        c[k << 1].sum += c[k].lazy*(mid - l + 1);
        c[k << 1 | 1].sum += c[k].lazy*(r - mid);

        c[k << 1].lazy += c[k].lazy;
        c[k << 1 | 1].lazy += c[k].lazy;

        c[k].lazy = 0;
    }
    void pushUp(int k)
    {
        c[k].sum = c[k << 1].sum + c[k << 1 | 1].sum;
    }
    // l, r是总区间 left, right是查询区间
    long long query(int k, int l, int r, int left, int right)
    {
        if (left <= l && r <= right)    return c[k].sum;

        pushDown(k, l, r);

        long long ans = 0;

        int mid = (l + r) >> 1;
        if (left <= mid)    ans += query(k << 1, l, mid, left, right);
        if (mid < right)    ans += query(k << 1 | 1, mid + 1, r, left, right);

        return ans;
    }
    void build(int k, int l, int r)
    {
        c[k].lazy = 0;
        if (l == r)
        {
            c[k].sum = a[l];  //a是原始数据数组
            return;
        }
        int mid = (l + r) >> 1;

        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);

        pushUp(k);
    }
    // l, r是总区间 left, right是查询区间，k是起始节点编号，val是更新的值
    void update(int k, int l, int r, int left, int right, int val)
    {
        if (left <= l && r <= right)
        {
            c[k].lazy += val;
            c[k].sum += val * (r - l + 1);
            return;
        }

        pushDown(k, l, r);

        int mid = (l + r) >> 1;
        if (left <= mid)    update(k << 1, l, mid, left, right, val);
        if (mid < right)    update(k << 1 | 1, mid + 1, r, left, right, val);

        pushUp(k);
    }
}

树状数组

区间求和+单点修改 logN

const int N = 1e5 + 5;
namespace BIT
{
    long long c[N];
    inline int lowbit(int x) { return x & (~x + 1); }
    // 查询[1, x]的区间和
    inline long long sum(int x)
    {
        long long res = 0;
        for (int i = x; i; i -= lowbit(i))  res += c[i];
        return res;
    }
    // 在x处加上val
    inline void add(int x, long long val)
    {
        for (int i = x; i < N; i += lowbit(i))  c[i] += val;
    }
}

ST表

离线查询区间最值 构造NlogN 查询1

#include <cstring>
const int N = 500005;
int a[N];
inline int max(int x, int y) { return x > y ? x : y; }
inline int min(int x, int y) { return x > y ? y : x; }
namespace ST
{
    int log[N];
    int stmin[N][30], stmax[N][30];
    // 快速查询log[n]
    void pre()
    {
        log[1] = 0;
        for (int i = 2; i < N; ++i)
        {
            log[i] = log[i - 1];
            if (i == (1 << (log[i] + 1)))   log[i]++;
        }
    }
    // 构造ST表
    void init()
    {
        memset(stmin, 0, sizeof(stmin));
        memset(stmax, 0, sizeof(stmax));
        for (int i = 1; i <= N; i++)
            stmax[i][0] = stmin[i][0] = a[i];
        for (int j = 1; j <= log[N]; j++)
            for (int i = 1; i + (1 << j) - 1 <= N; i++)
            {
                stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << (j - 1))][j - 1]);
                stmin[i][j] = min(stmin[i][j - 1], stmin[i + (1 << (j - 1))][j - 1]);
            }
    }
    // 查询区间[l, r]的最大值
    int queryMax(int l, int r)
    {
        int k = log[r - l + 1];
        return max(stmax[l][k], stmax[r - (1 << k) + 1][k]);
    }
    // 查询区间[l, r]的最小值
    int queryMin(int l, int r)
    {
        int k = log[r - l + 1];
        return min(stmin[l][k], stmin[r - (1 << k) + 1][k]);
    }
}