线段树的概念

线段树是一种用于区间处理的数据结构，用二叉树来构造
线段树是二叉树，一个区间每次被折一半往下分，所有最多分 $图片说明$ 次就能找到。这就是线段树效率高的原因，使用了二叉树折半查找的方法。

线段树的基本操作

单点修改，区间查询

【max】给定一个n（n <= 100000）个元素的数组A，有m（m <= 100000）个操作，共两种操作：

单点修改：（C a c）表示将第a个元素变成c；
区间查询：（Q a b）表示询问区间[a, b]的最大值；

const int maxn = 2e5+1;
int p[maxn];

struct node {
    int l, r, val;
    node () {}
    node (int l, int r, int val): l(l), r(r), val(val){}
    node operator+ (const node n1) { // 区间合并 -- 求最值
        return node(l, n1.r, max(val, n1.val));
    }
}pos[maxn << 2];

void BuildTree(int root, int l, int r) { // 建树
    if (l == r) {
        pos[root] = node(l, r, p[l]);
        return ;
    }
    int mid = l + r >> 1;
    BuildTree(root<<1, l, mid);
    BuildTree(root<<1|1, mid + 1, r);
    pos[root] = pos[root<<1] + pos[root<<1|1];
}


void UpData(int root, int l, int r, int u, int val) { // 单点修改
    if (l == r) {
        pos[root].val  = val;
        return ;
    }
    int mid = l + r >> 1;
    if (mid >= u) UpData(root<<1, l, mid, u, val);
    else if (mid < u) UpData(root<<1|1, mid+1, r, u, val);
    pos[root] = pos[root<<1] + pos[root<<1|1];
}

node Query(int root, int l, int r, int ql, int qr) { // 区间查询
    if (l == ql && r == qr) return pos[root];
    int mid = l + r >> 1;
    if (mid >= qr) return Query(root<<1, l, mid, ql, qr);
    if (mid <  ql) return Query(root<<1|1, mid+1, r, ql, qr);
    return Query(root<<1, l, mid, ql, mid) + Query(root<<1|1, mid+1, r, mid+1, qr);
}

区间修改，区间查询 —— 懒惰标记

【sum】给定一个n（n <= 100000）个元素的数组A，有m（m <= 100000）个操作，共两种操作：

区间修改：（A a b c）表示将区间[a, b]的每个元素加上一个值c；
区间查询：（Q a b）表示询问区间[a, b]的元素和；

const int maxn = 2e5+1;
int p[maxn];

struct node {
    int l, r;
    long long val, lazy;
    node () {lazy = 0;}
    node (int l, int r, long long val): l(l), r(r), val(val){lazy = 0;}
    node operator+ (const node n1) { // 区间合并 -- 求和
        return node(l, n1.r, val + n1.val);
    }
}pos[maxn << 2];

void BuildTree(int root, int l, int r) { // 建树
    if (l == r) {
        pos[root] = node(l, r, p[l]);
        return ;
    }
    pos[root].lazy = 0; // 清空懒惰标记
    int mid = l + r >> 1;
    BuildTree(root<<1, l, mid);
    BuildTree(root<<1|1, mid + 1, r);
    pos[root] = pos[root<<1] + pos[root<<1|1];
}

void PushDown(int root) { // 懒惰更新
    if (pos[root].lazy) {
        pos[root<<1].val += pos[root].lazy*(pos[root<<1].r-pos[root<<1].l+1);
        pos[root<<1].lazy += pos[root].lazy;
        pos[root<<1|1].val += pos[root].lazy*(pos[root<<1|1].r-pos[root<<1|1].l+1);
        pos[root<<1|1].lazy += pos[root].lazy;
        pos[root].lazy = 0;
    }
}

void UpData(int root, int l, int r, int ul, int ur, int val) { // 区间更新
    if (l == ul && r == ur) {
        pos[root].val += val*(r-l+1);
        pos[root].lazy += val;
        return ;
    }
    PushDown(root);
    int mid = l + r >> 1;
    if (mid >= ur) UpData(root<<1, l, mid, ul, ur, val);
    else if (mid < ul) UpData(root<<1|1, mid+1, r, ul, ur, val);
    else {
        UpData(root<<1, l, mid, ul, mid, val);
        UpData(root<<1|1, mid+1, r, mid+1, ur, val);
    }
    pos[root] = pos[root<<1] + pos[root<<1|1];
}

node Query(int root, int l, int r, int ql, int qr) { // 区间查询
    if (l == ql && r == qr) return pos[root];
    PushDown(root);
    int mid = l + r >> 1;
    if (mid >= qr) return Query(root<<1, l, mid, ql, qr);
    if (mid <  ql) return Query(root<<1|1, mid+1, r, ql, qr);
    return Query(root<<1, l, mid, ql, mid) + Query(root<<1|1, mid+1, r, mid+1, qr);
}

/* 
int Query(int root, int l, int r, int q) { // 单点查询
    if (l == r) return pos[root].val;
    PushDown(root);
    int mid = l + r >> 1;
    if (mid >= q) return Query(root<<1, l, mid, q);
    return Query(root<<1|1, mid+1, r, q);
}
*/

线段树拓展

1. 不连续区间修改，单点查询 —— 分组线段树

【p[x]】给定一个n（n <= 50000）个元素的数组P，有m（m <= 50000）个操作，共两种操作：

不连续区间修改：（A a b k c）表示将区间[a, b]中满足(i-a)%k == 0 的元素加上一个值c；（其中k<=10）
单点查询：（Q a b）表示询问区间[a, b]的元素和；

注：建k*(k+1)/2棵树，每次修改只对一棵树进行修改，每次查询要对所有有效树都进行一次查询。

#include<cstdio>

using namespace std;
const int maxn = 5e4+1;
int p[maxn], d[] = {0,0,1,3,6,10,15,21,28,36,45};
int pos[maxn<<2][55]; // 单点查询-线段树

void BuildTree(int root, int l, int r, int rt) { // 建树
    pos[root][rt] = 0;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    BuildTree(root<<1, l, mid, rt);
    BuildTree(root<<1|1, mid + 1, r, rt);
}

void PushDown(int root, int rt) { // 最·懒惰更新
    if (pos[root][rt]) {
        pos[root<<1][rt] += pos[root][rt];
        pos[root<<1|1][rt] += pos[root][rt];
        pos[root][rt] = 0;
    }
}

void UpData(int root, int l, int r, int ul, int ur, int val, int rt) { // 区间修改
    if (l == ul && r == ur) {
        pos[root][rt] += val;
        return ;
    }
    PushDown(root, rt);
    int mid = l + r >> 1;
    if (mid >= ur) UpData(root<<1, l, mid, ul, ur, val, rt);
    else if (mid < ul) UpData(root<<1|1, mid+1, r, ul, ur, val, rt);
    else {
        UpData(root<<1, l, mid, ul, mid, val, rt);
        UpData(root<<1|1, mid+1, r, mid+1, ur, val, rt);
    }
}

int Query(int root, int l, int r, int q, int rt) { // 单点查询
    if (l == r) return pos[root][rt];
    PushDown(root, rt);
    int mid = l + r >> 1;
    if (mid >= q) return Query(root<<1, l, mid, q, rt);
    return Query(root<<1|1, mid+1, r, q, rt);
}

int main() {
    int n; while(scanf("%d", &n) != EOF) {
        for(int i = 0; i < 55; ++ i) { // 建55课线段树
            BuildTree(1, 1, n, i);
        }
        for(int i = 1; i <= n; ++ i) {
            scanf("%d", &p[i]);
        }
        int m; scanf("%d", &m);
        while(m --) {
            int op; scanf("%d", &op);
            if (op == 1) {
                int a, b, k, c; scanf("%d%d%d%d", &a, &b, &k, &c);
                UpData(1, 1, n, a, b, c, d[k]+a%k);
            }
            else {
                int x, res = 0; scanf("%d", &x);
                for(int i = 1; i <= 10; ++ i) {
                    res += Query(1, 1, n, x, d[i]+x%i);
                }
                printf("%d\n", res + p[x]);
            }
        }
    }
    return 0;
}

2. 离散化

sort(g + 1, g + n + 1);            // 排序
m = unique(g+1, g+1+n) - (g+1);    // 去重
for(int i = 1; i <= n; ++ i) {     
    p[i] = lower_bound(g+1, g+m+1, p[i]) - g;
}

3. RMQ 问题

RMQ（Range Minimum/Maximum Query），即区间最值查询。ST表（Tarjan的Sparse-Table算法）求解 RMQ 一般用较长时间做预处理init(n)，时间复杂度为O(nlogn)，然后可以在O(1)的时间内处理每次查询RMQ(l,r)。

const int maxn = 1e6+1;

int a[maxn];
int d[maxn][32]; // 从第i个数起连续2^j个数中的最小值

int init(int n) { // 预处理
    for(int i = 1; i <= n; ++ i) {
        d[i][0] = a[i];
    }
    for(int i = n; i >= 1; -- i) {
        for(int j = 1; i + (1<<j-1) <= n; ++ j) {
            d[i][j] = min(d[i][j-1], d[i+(1<<j-1)][j-1]);
        }
    }
}

int RMQ(int l, int r) {
    int k = 31 - __builtin_clz(r-l+1);
    return min(d[l][k], d[r-(1<<k)+1][k]);
}