线段树

https://www.cnblogs.com/jason2003/p/9676729.html
已知一个数组 $a[i]$ ，对其进行以下操作：
$(1)$ 单点查询：求 $a[i]$ 。
$(2)$ 单点修改：更改 $a[i]$ 的值。
$(3)$ 区间查询：求区间[l,r)的 $a[i]$ 和。
$(4)$ 区间修改：把区间[l,r)中的每个 $a[i]$ 都加上相同的值。
$(5)$ 区间修改（加强版）：把区间[l,r)中的每个 $a[i]$ 都加、乘上相同的值，以及开根号。

用一个大的二叉树来存区间的 $a[i]$ 和，根结点的两个儿子二分整个数组，它儿子的儿子再二分它的儿子，直到叶子结点为 $a[i]$ 。
可以证明，这棵树的空间不超过 $a[i]$ 大小的四倍。

建树：设一个标号 $i$ （从1开始），对于每个结点 $tree[i]$ ，它的左儿子为 $tree[i*2]$ ，右儿子为 $tree[i*2+1]$ 。利用 $sum[i]=sum[i*2]+sum[i*2+1]$ 递归地计算每个结点的值。

1.单点修改+区间查询：https://www.luogu.org/problem/P3374
区间查询：从根结点开始，如果要查的区间与某个结点的左子结点相交，则递归地查左子结点，反之查右子结点；直到某个子结点的区间完全被要查的区间包含，返回该子结点的值。
单点修改：递归地确定要查的元素对应的叶结点，将这个结点的值改变，然后回溯此过程经过的路径，更新路径上结点的值： $sum[i]=sum[i*2]+sum[i*2+1]$

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 500010;
int n, m;
int a[maxn];
struct Tree {
    int l;
    int r;
    int sum;
}tree[maxn*4];
void build(int i, int l, int r) {//建树
    tree[i].l = l;
    tree[i].r = r;
    if (l == r) {
        tree[i].sum = a[l];//注意这里是a[l]，不是a[i]！
        return;
    }
    int mid = (l + r) / 2;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
    tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;
}
int search(int i, int l, int r) {//区间查询
    if (tree[i].l >= l && tree[i].r <= r) return tree[i].sum;
    if (tree[i].r<l || tree[i].l>r) return 0;
    int s = 0;
    if (tree[i * 2].r >= l) s += search(i * 2, l, r);
    if (tree[i * 2 + 1].l <= r)s += search(i * 2 + 1, l, r);
//用左子树的右端点和右子树的左端点控制，下同
    return s;
}
void add(int i, int dis, int k) {//单点修改
    if (tree[i].l == tree[i].r) {
        tree[i].sum += k;
        return;
    }
    if (dis <= tree[i * 2].r) add(i * 2, dis, k);
    else add(i * 2 + 1, dis, k);
    tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;
    return;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
    build(1, 1, n);
    int t, x, y, k;
    for (int i = 1; i <= m; i++) {
        scanf("%d",&t);
        if (t == 1) {
            scanf("%d%d", &x, &k);
            add(1, x, k);
        }
        else {
            scanf("%d%d",&x,&y);
            printf("%d\n", search(1, x, y));
        }
    }
    return 0;
}

时间复杂度： $O(nlogn)$ 。
注意：虽然时间复杂度和树状数组一样，但是明显比树状数组慢（用cin会超时），占空间多（4倍），而且写的也多，所以能用树状数组不要用线段树。

2.区间修改+单点查询：https://www.luogu.org/problem/P3368
同理树状数组，建树的时候除了叶子结点储存 $a[l]$ 外，其他结点都置为0。区间修改时，如果当前区间完全被目标区间包含，将其sum加k；单点查询时，把一路的sum都加起来即可。
代码：

#pragma warning(disable:4996)
#include<cstdio>
const int maxn = 500010;
int n, m;
int a[maxn];
struct Tree {
    int l;
    int r;
    int sum;
}tree[maxn*4];
void build(int i, int l, int r) {
    tree[i].l = l;
    tree[i].r = r;
    if (l == r) {
        tree[i].sum = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
}
void add(int i, int l, int r, int x) {
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].sum += x;
        return;
    }
    if (tree[i * 2].r >= l) add(i * 2, l, r, x);
    if (tree[i * 2 + 1].l <= r) add(i * 2 + 1, l, r, x);
}
int search(int i, int dis) {
    if (tree[i].l == tree[i].r) return tree[i].sum;
    int res = tree[i].sum;  //注意res要从当前的sum开始加，初值不能设为0
    if (dis <= tree[i * 2].r) res += search(i * 2, dis);
    else res += search(i * 2 + 1, dis);
    return res;
}
int t, x, y, k;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &t);
        if (t == 1) {
            scanf("%d%d%d", &x, &y, &k);
            add(1, x, y, k);
        }
        else {
            scanf("%d", &x);
            printf("%d\n", search(1, x));
        }
    }
    return 0;
}

3.区间修改+区间查询：https://www.luogu.org/problem/P3372
不能将以上两个模板合起来：如果跨区间先修改再查询，会查询到没有修改的结点，如1，2，3，4，先修改1，2，3的值，修改了12结点和3结点；再查询2，3，4的值，查询了2结点和34结点，结果和没修改一样。
正确算法：
给每个结点加一个懒标记tree[i].lz。
定义一种操作下传懒标记（push_down(i)）：让tree[i]的左右子树的sum加上tree[i].lz * len，并让它们的懒标记加上tree[i].lz（相当于用tree[i].lz对tree[i]的左右子树做了修改），最后把tree[i]的懒标记清零。
因为是区间查询，建树和模板1一样。
修改的时候，如果当前结点被目标区间完全包含，将tree[i].sum+=x*len，并将tree[i].lz+=k；如果当前结点没有被完全包含，先push_down(i)，再搜索与目标区间有交集的左子树或者右子树，最后更新tree[i].sum。
查询的时候，如果当前结点被目标结点完全包含，就返回tree[i].sum；如果完全没交集，返回0；否则先下传懒标记，再进行和模板1一样的区间查询。
这样的好处是，对一整块的区间进行修改后，记住了修改的值，等到查询或者下次修改的时候，先把上次修改的值传下去，这样就不会出现跨区间查询查到没有修改的结点的问题了。
代码：

#pragma warning(disable:4996)
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int n, m;
int a[maxn];
struct Tree {
    int l;
    int r;
    ll lz;
    ll sum;
    int len() {
        return r - l + 1;
    }
}tree[maxn*4];
void build(int i, int l, int r) {
    tree[i].l = l;
    tree[i].r = r;
    if (l == r) {
        tree[i].sum = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
    tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;
}
void push_down(int i) {
    for (int j = i * 2; j <= i * 2 + 1; j++) {
        tree[j].sum += tree[i].lz*tree[j].len();
        tree[j].lz += tree[i].lz;
    }
    tree[i].lz = 0;
}
void add(int i, int l, int r, int x) {
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].sum += x * tree[i].len();
        tree[i].lz += x;
        return;
    }
    push_down(i);
    if (tree[i * 2].r >= l) add(i * 2, l, r, x);
    if (tree[i * 2 + 1].l <= r) add(i * 2 + 1, l, r, x);
    tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;
}
ll search(int i, int l, int r) {
    if (tree[i].l >= l && tree[i].r <= r) return tree[i].sum;
    if (tree[i].r<l || tree[i].l>r) return 0;
    push_down(i);
    ll res = 0;
    if (tree[i * 2].r >= l) res += search(i * 2, l, r);
    if (tree[i * 2 + 1].l <= r) res += search(i * 2 + 1, l, r);
    return res;
}
int t, x, y, k;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &t);
        if (t == 1) {
            scanf("%d%d%d", &x, &y, &k);
            add(1, x, y, k);
        }
        else {
            scanf("%d%d", &x, &y);
            printf("%lld\n",search(1, x, y));
        }
    }
    return 0;
}

4.区间加法+区间乘法+区间查询：https://www.luogu.org/problem/P3373
乘法和加法运算独立，且对取模保持运算，所以修改的时候分开做没有影响，问题是push_down的时候需要传两个懒标记，这样就与运算顺序有关了。
首先，假设对一列数 $a_1,a_2,..a_n$ 先都乘 $k_1$ ，再都加 $k_2$ ，和由 $\sum_{i=1}^na_i$ 变成了 $k_1\sum_{i=1}^na_i+\sum_{i=1}^nk_2=k_1S_n+nk_2$ ；若先加 $k_2$ ，再乘 $k_1$ ，则和变成 $k_1S_n+nk_2k_1$ ，对比上式发现只有第二项多乘了一个 $k_1$ ，相当于把 $k_2$ 换成了 $k_2k_1$ 。
所以，每次做乘法运算把乘法的懒标记mlz乘x的时候，顺便把加法的懒标记plz也乘x，这样就都统一成了 $k_2k_1$ 了，就可以带入上面的第一个式子计算.
同样，在push_down的时候更新plz，也要先乘新的mlz再加上新的plz。
因为 $K_1(k_1S_n+nk_2)+K_2n=(K_1k_1)S_n+(K_1k_2+K_2)n$ ，推出 $k_1'=K_1k_1，k_2'=K_1k_2+K_2$ 。

#pragma warning(disable:4996)
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int n, m, p;
ll a[maxn];
struct Tree {
    int l;
    int r;
    ll sum;
    ll plz;
    ll mlz;
    int len() {
        return r - l + 1;
    }
}tree[maxn*4];
void build(int i, int l, int r) {
    tree[i].l = l;
    tree[i].r = r;
    tree[i].mlz = 1;
    if (l == r) {
        tree[i].sum = ll(a[l]) % p;
        return;
    }
    int mid = (l + r) / 2;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
    tree[i].sum = (tree[i * 2].sum + tree[i * 2 + 1].sum) % p;
}
void push_down(int i) {
    ll mlz = tree[i].mlz, plz = tree[i].plz;
    for (int j = i * 2; j <= i * 2 + 1; j++) {
        tree[j].sum = (tree[j].sum*mlz + tree[j].len()*plz) % p;
        tree[j].mlz = (tree[j].mlz*mlz) % p;
        tree[j].plz = (tree[j].plz*mlz + plz) % p;
    }
    tree[i].plz = 0;
    tree[i].mlz = 1;
}
void mul(int i, int l, int r, int x) {
    if (tree[i].r<l || tree[i].l>r) return;
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].sum = (tree[i].sum*x) % p;
        tree[i].mlz = (tree[i].mlz*x) % p;
        tree[i].plz = (tree[i].plz*x) % p;
        return;
    }
    push_down(i);
    if (tree[i * 2].r >= l) mul(i * 2, l, r, x);
    if (tree[i * 2 + 1].l <= r) mul(i * 2 + 1, l, r, x);
    tree[i].sum = (tree[i * 2].sum + tree[i * 2 + 1].sum) % p;
}
void add(int i, int l, int r, int x) {
    if (tree[i].r<l || tree[i].l>r) return;
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].sum += (tree[i].len()*x) % p;
        tree[i].plz = (tree[i].plz + x) % p;
        return;
    }
    push_down(i);
    if (tree[i * 2].r >= l) add(i * 2, l, r, x);
    if (tree[i * 2 + 1].l <= r) add(i * 2 + 1, l, r, x);
    tree[i].sum = (tree[i * 2].sum + tree[i * 2 + 1].sum) % p;
}
ll search(int i, int l, int r) {
    if (tree[i].r<l || tree[i].l>r) return 0;
    if (tree[i].l >= l && tree[i].r <= r) {
        return tree[i].sum;
    }
    push_down(i);
    ll sum = 0;
    if (tree[i*2].r >= l) sum += search(i * 2, l, r) % p;
    if (tree[i*2+1].l <= r) sum += search(i * 2 + 1, l, r) % p;
    return sum % p;
}
int t, x, y, k;
int main() {
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &t);
        if (t == 1) {
            scanf("%d%d%d", &x, &y, &k);
            mul(1, x, y, k);
        }
        else if (t == 2) {
            scanf("%d%d%d", &x, &y, &k);
            add(1, x, y, k);
        }
        else {
            scanf("%d%d", &x, &y);
            printf("%lld\n", search(1, x, y)%p);
        }
    }
    return 0;
}

5.区间根号：https://www.lydsy.com/JudgeOnline/problem.php?id=3211
先欠着……

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,937评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,503评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,712评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,668评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,677评论 5赞 366
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,601评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,975评论 3赞 396
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,637评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,881评论 1赞 298
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,621评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,710评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,387评论 4赞 319
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,971评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,947评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,189评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,805评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,449评论 2赞 342

线段树

推荐阅读更多精彩内容