本文正在参与「金石计划 . 瓜分6万现金大奖」

从原理到实战带你知道线段树：根底篇

零、序言——万物滴开篇

或许你是苦于书面考试的打工人，或许你是步入算法圈不久的小小萌新（我也是萌新） ，或许你是在网上搜索数据结构课设的倒运学生。不管怎样样，看完本篇文章，期望对您有所协助。

从原理到实战带你认识线段树：基础篇

走起！

观前提示：看本文章最好有一定的二叉树根底（至少要会递归遍历树的程度）和算法根底（咋的也得知道时刻复杂度是什么）

线段树 是算法比赛中非常常见一种的数据结构，功能强大，学术一点的话说便是：常用的用来维护 区间信息 的数据结构。线段树 能够在较小的时刻复杂度内完成单点修正、区间修正、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

没听懂？没事，曾经我也听不懂，让咱们来——

一、举个栗子

给你一个长度为 n 的数组，有 q 次问询，每次问询给你一个规模：l 和 r ,让你求出数组中第l个数到第r个总和是多少。

关于每次问询，咱们能够从第l个数一直累加到第r个数，这样就能轻轻松松得出成果，可是这么做的时刻复杂度是O(n) ，一共q次问询，那么总的时刻复杂度便是O(n*q) 。关于数据大的状况下，这样是无法经过标题的。可是假如运用 线段树 ，就能够把单次问询的时刻复杂度减小到 O(logn) ，这样q次问询下来，总的时刻复杂度只需 O(q*logn) ，非常快哦！

提到这儿，或许有同学学的比较好，学过 前缀和 算法，他不服气，说运用前缀和，单次问询的复杂度只需 O(1) ，总的复杂度便是 O(q) ，不比这个线段树还要快吗？

假如是当时这一题，那么当然是前缀和比线段树要快，无可否认（线段树：我成了？ ），可是，要是给标题加上一个条件之后，你再看：

给你一个长度为 n 的数组，有 q 次操作，操作有两种：

  • 1：给你一个下标i和一个数x，需求你把数组中第i个数加上x；

  • 2：给你一个规模：l 和 r ,让你求出数组中第l个数到第r个总和是多少。

这一题和上一题不相同的是，多了个修正数组的操作。而咱们知道，前缀和是必须要预处理出前缀和数组的，预处理的复杂度是O(n) ，可是正常状况下，只用预处理一次，所以这一点咱们一般能够忽略不计。可这儿，数组或许随时会发生变化，假如数组发生了变化，那之前预处理出的前缀和数组就不对了，由此得到的区间和答案也不正确。除非每次修正后，从头预处理出前缀和数组，可是这样，单次问询的复杂度就从O(1) 退化到了O(n) ，总复杂度变成了O(n*q) 。

前缀和做法翻车哩！

此刻咱们回头看看刚刚的小丑线段树，线段树的问询是在O(logn) 中得出成果，但还有一点：线段树的修正也是O(logn) ，而且修正往后得出成果的复杂度仍然是O(logn) 。所以关于线段树来说，这道题总的复杂度依旧是O(logn) ！线段树扳回一城！

从原理到实战带你认识线段树：基础篇

而就像咱们开端说的，不但是求区间和，区间最值什么的也能在O(logn) 的复杂度内得出成果，不说单点修正数组的值，哪怕是修正数组的一段区间，它也能够在O(logn) 的复杂度内完成！

那么，线段树是怎样做到这一点的呢？

二、线段树——什么树？

实际上，线段树其实也便是一个二叉树。

首要，咱们先来聊一聊它的根底形状：二叉树。

二叉树算是非常根底的数据结构了，树如其名，每一个节点最多只需两个孩子，一左一右，即二叉。图中便是一个最简单的二叉树：

从原理到实战带你认识线段树：基础篇

那么线段树是怎样做到能在O(n*logn) 的复杂度上得到区间和的呢？

  1. 咱们先给上图这二叉树的两个孩子分别赋一个值：x 和 y。
  2. 那么咱们想求出这两个点的总和，只需求：root->left->val + root->right->val。
  3. root的左右两个孩子都有值了，但root仍是空荡荡的，咱们不如把这个总和当作root节点的值。

此刻，这个二叉树的状况是：

从原理到实战带你认识线段树：基础篇

那么之后，假如想知道root的左右俩孩子的值的总和，咱们并不需求遍历到这两个点，只需直接遍历到root上，就能够得出成果了。

现在你或许觉得没什么大不了的，也才两个点，我直接遍历他们和遍历一个点也没什么差异。

好，线段树觉得自己被瞧不起了，它开端成长：

从原理到实战带你认识线段树：基础篇
现在想知道a、b、c、d四个点的总和，只需求看最上面的那一个点就行了。

还不够？它持续成长：

从原理到实战带你认识线段树：基础篇
再长：

从原理到实战带你认识线段树：基础篇

再长：

算了吧再长就放不下了。

这便是线段树的运行方式，咱们就能够这样，一层一层的持续套下去，最终，假如想知道整个数组的总和，只需走到最上面的那个点就行，而不必遍历整个数组。这功率，显而易见的高。

线段树中的 ”树“ 咱们已经体会到了，可是咱们还有疑问。

三、线段树——何为线段？

首要阐明一点：线段树的叶子，便是数组的元素

（为了方便，咱们拿小一点的树来做介绍）

假如此刻有一个长度为4的数组，它的元素分别为：a，b，c，d。那么在线段树中表现出来的便是：

从原理到实战带你认识线段树：基础篇

然后咱们又知道，元素a在数组中的出现规模是 {1,1} ，元素b的出现规模是 {2,2} ，c的是 {3,3} ，d是 {4,4} 。

咱们依据这一点，把线段树用另一种方式表现出来：

从原理到实战带你认识线段树：基础篇

每个节点上的规模，就表明了这个节点统辖的数组规模。

比方a是{1，1}，b是{2，2}，那么他们的父亲统辖的规模便是{1，2}，假如咱们想知道数组中第一个数到第二个数的总和，只需求走到点e就能够了。以此类推。

而这，便是线段树中的——线段。 （说是线段，不如说规模更适宜。）

在线段树中，每一个节点都有其担任的一个规模，当咱们遇到区间查问询题的时候，只需走到对应的节点就能够得出成果了。

什么，你问我线段树上没有节点担任{1，3}规模，你想问{1，3}规模的总和怎样办？那当然是节点e的成果加上节点c的成果了啊，笨猪猪捏(～￣(OO)￣)ブ。

咱们每次问询都是从上往下遍历树的节点，而咱们知道，关于一个有n个叶子的二叉树，它的深度是log2(n) ，所以不论是查询仍是修正，咱们都只用跑log2(n) 层，时刻复杂度就为：O(logn) 。

要是看到这儿，对线段树终于有所了解，有恍然大悟之感的同学能不能在屏幕前给咱鼓个掌捏。

从原理到实战带你认识线段树：基础篇

好哩，这下线段树的原理都解释清楚啦！！！接下来终于要到了——

四、代码是如何完成的？

由于的各位友友或许都是非算法比赛选手，比起数组方式的树或许更习惯结构体方式，所以这一环节我会用结构体方式的代码做解说（数组方式的代码我会在最终面说一下）

这是最重要也最难的一节啦（由于代码太多了，或许有点看不过来）！经过这一节你就成功啦！加油！！

咱们仍是先回到二叉树，一般咱们写二叉树的代码是：

别问我为啥不必力扣的二叉树结构体，指针那么厌恶的玩意我不想碰

struct TreeNode {
    int val;
    //或许有同学不理解为什么这两个指向孩子的是整形变量不是指针
    //left和right是数组Node的下标，所以精确来说这个节点的孩子不是left，而是Node[left]
    int left,right;
 }Node[N];

相较于一般的二叉树，线段树的结构体代码多出了两个变量，即代表规模的：l（表明规模左端点） 和 r（表明规模右端点）

代码如下：

struct TreeNode {
    int val;
    int left,right;
    int l,r;
 }Node[N];

总节点（便是最顶上的那一个），它的下标为1，即Node[1]。

关于线段树类型的题（像咱们第一节举那个的栗子），一般都会先给咱们一个数组。那么，咱们首要要做的便是使用这个数组来生成线段树：

  1. 假如数组的长度为n，那么总节点（Node[1]）的开始规模是 {1，n}
  2. 然后咱们将规模一分为二，左孩子的规模便是： {1，mid} ，右孩子的规模便是： {mid+1，n} 。
  3. 到了孩子节点，咱们持续分，以此类推。
  4. 当到了某个节点，规模变成了 {l，l} （即左右端点相等，表明这个点只代表一个数），就阐明这个节点便是叶子节点，咱们把数组的值赋给它（规模是啥就把关于的值给它，可不是乱赋值嗷）
  5. 当某个节点的左右节点都赋完值了，他们的父亲节点的值，便是这两个孩子节点的值的总和。
代码如下：
struct TreeNode {
   int val;
   int left, right;
   int l, r;
}Node[N];
​
//a是标题给的数组;idx是建树过程中，用于给各个树打上序号
int a[N],idx = 1;
void build_tree(int pos)
{
    //假如左右端点相同，阐明这是叶子节点
   if (Node[pos].l == Node[pos].r)
   {
       //把数组的值赋给他
     Node[pos].val = a[Node[pos].l];
     return;
   }
   //假如不相同，阐明规模还能往下分
   int mid = (Node[pos].l + Node[pos].r) / 2;
   //左右孩子的下标
   int left = ++idx, right = ++idx;
   Node[pos].left = left;
   Node[pos].right = right;
​
    //左孩子的规模
   Node[left].l = Node[pos].l;
   Node[left].r = mid;
    //右孩子的规模
   Node[right].l = mid + 1;
   Node[right].r = Node[pos].r;
​
    //递归到下一层
   build_tree(left);
   build_tree(right);
    //当时节点的值，便是两个孩子的值相加
   Node[pos].val = Node[left].val + Node[right].val;
}

至于修正，咱们也是遍历到对应的点，比方要改的是数组的第3个值，那么咱们就找到树中，规模为{3，3}的那个叶子并修正。

void revise(int pos, int l,  int x)
{
    //假如这便是咱们要找的规模，修正这个节点的值
   if (Node[pos].l == l && Node[pos].r == l)
   {
     Node[pos].val += x;
     return;
   }
   //假如不是，咱们就看咱们要找的点，是当时点的左孩子仍是右孩子
   int mid = (Node[pos].l + Node[pos].r) / 2;
   if (l <= mid)revise(Node[pos].left, l, x);
   else revise(Node[pos].right, l, x);
    //由于叶子节点被修正，那么上面一切受影响的点的值都要更新
   int left = Node[pos].left, right = Node[pos].right;
   Node[pos].val = Node[left].val + Node[right].val;
}

最终是问询一整个区间的和。

int calc(int pos, int l, int r)
{
    //假如这便是咱们要找的规模，回来这个节点的值
   if (Node[pos].l == l && Node[pos].r == r)
   {
     return Node[pos].val;
   }
   //假如不是，就依据当时节点的规模，判别咱们下一步该往左走仍是右走
   int mid = (Node[pos].l + Node[pos].r) / 2;
   //假如规模全在左边，就直接去左节点
   if (r <= mid)return calc(Node[pos].left, l, r);
   else
       //假如规模全在右边，就直接去右节点
     if (l > mid)return calc(Node[pos].right, l, r);
     else
     {
         //假如规模既在左又在右，则分隔跑。留意这儿要修正规模。
       int x = calc(Node[pos].left, l, mid);
       int y = calc(Node[pos].right, mid + 1, r);
       //回来两边的成果
       return x + y;
     }
}

到此，这便是线段树：单点修正+区间查询的悉数模板代码了。

咱们来提交一下这一题：P3374 【模板】树状数组 1（甭管为什么标题叫树状数组）

标题总代码：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
​
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
​
#define endl '\n'
#define int ll
#define all(a) a.begin(),a.end()
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;
​
struct TreeNode {
   int val;
   int left, right;
   int l, r;
}Node[N];
​
//a是标题给的数组;idx是建树过程中，用于给各个树打上序号
int a[N],idx = 1;
void build_tree(int pos)
{
    //假如左右端点相同，阐明这是叶子节点
   if (Node[pos].l == Node[pos].r)
   {
       //把数组的值赋给他
     Node[pos].val = a[Node[pos].l];
     return;
   }
   //假如不相同，阐明规模还能往下分
   int mid = (Node[pos].l + Node[pos].r) / 2;
   //左右孩子的下标
   int left = ++idx, right = ++idx;
   Node[pos].left = left;
   Node[pos].right = right;
​
    //左孩子的规模
   Node[left].l = Node[pos].l;
   Node[left].r = mid;
    //右孩子的规模
   Node[right].l = mid + 1;
   Node[right].r = Node[pos].r;
​
    //递归到下一层
   build_tree(left);
   build_tree(right);
    //当时节点的值，便是两个孩子的值相加
   Node[pos].val = Node[left].val + Node[right].val;
}
​
void revise(int pos, int l,  int x)
{
    //假如这便是咱们要找的规模，修正这个节点的值
   if (Node[pos].l == l && Node[pos].r == l)
   {
     Node[pos].val += x;
     return;
   }
   //假如不是，咱们就看咱们要找的点，是当时点的左孩子仍是右孩子
   int mid = (Node[pos].l + Node[pos].r) / 2;
   if (l <= mid)revise(Node[pos].left, l, x);
   else revise(Node[pos].right, l, x);
    //由于叶子节点被修正，那么上面一切受影响的点的值都要更新
   int left = Node[pos].left, right = Node[pos].right;
   Node[pos].val = Node[left].val + Node[right].val;
}
​
int calc(int pos, int l, int r)
{
    //假如这便是咱们要找的规模，回来这个节点的值
   if (Node[pos].l == l && Node[pos].r == r)
   {
     return Node[pos].val;
   }
   //假如不是，就依据当时节点的规模，判别咱们下一步该往左走仍是右走
   int mid = (Node[pos].l + Node[pos].r) / 2;
   //假如规模全在左边，就直接去左节点
   if (r <= mid)return calc(Node[pos].left, l, r);
   else
       //假如规模全在右边，就直接去右节点
     if (l > mid)return calc(Node[pos].right, l, r);
     else
     {
         //假如规模既在左又在右，则分隔跑。留意这儿要修正规模。
       int x = calc(Node[pos].left, l, mid);
       int y = calc(Node[pos].right, mid + 1, r);
       //回来两边的成果
       return x + y;
     }
}
​
signed main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
  
   int n, q, op, x, y;
   cin >> n >> q;
   for (int i = 1; i <= n; i++)cin >> a[i];
   Node[1].l = 1, Node[1].r = n;
   build_tree(1);
   for (int i = 1; i <= q; i++)
   {
     cin >> op >> x >> y;
     if (op == 1)
       revise(1, x, y);
     else
       cout << calc(1, x, y) << endl;
   }
   return 0;
}

从原理到实战带你认识线段树：基础篇

哈！满分！太棒啦！

为了比照，咱们运用暴力做法看看能不能经过：

从原理到实战带你认识线段树：基础篇

能够看出，小型数据仍是能够经过的，可是数据大了就会超时。

顺带一提，实际上结构体做线段树不太优，更常见的做法是用数组模仿，详细细节能够看注释，代码如下：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
​
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
​
#define endl '\n'
#define int ll
#define all(a) a.begin(),a.end()
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;
​
//f的效果就相当于Node的val
//这儿，假如当时节点的编号是k，那么它的左孩子是k+k，右孩子是k+k+1
//假如数组长度为n，那么线段树的数组长度则需求是4*n
int a[N], f[4 * N];
//数组方式的线段树，每个函数，开头都是三个变量：当时节点的编号k，当时节点的统辖区间的左端点l和右端点r
void build_tree(int k, int l, int r)
{
   if (l == r)
   {
     f[k] = a[l];
     return;
   }
   int mid = (l + r) / 2;
   build_tree(k + k, l, mid);
   build_tree(k + k + 1, mid + 1, r);
   f[k] = f[k + k] + f[k + k + 1];
}
void revise(int k, int l, int r, int x, int y)
{
   if (l == r)
   {
     f[k] += y;
     return;
   }
   int mid = (l + r) / 2;
   if (x <= mid)revise(k + k, l, mid, x, y);
   else revise(k + k + 1, mid + 1, r, x, y);
   f[k] = f[k + k] + f[k + k + 1];
}
int calc(int k, int l, int r, int x, int y)
{
   if (l == x && r == y)return f[k];
   int mid = (l + r) / 2;
   if (y <= mid)return calc(k + k, l, mid, x, y);
   else
     if (x > mid)return calc(k + k + 1, mid + 1, r, x, y);
     else return calc(k + k, l, mid, x, mid) + calc(k + k + 1, mid + 1, r, mid + 1, y);
}
​
signed main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
  
   int n, q, op, x, y;
   cin >> n >> q;
   for (int i = 1; i <= n; i++)cin >> a[i];
   //同样的，1号点的规模便是1~n
   build_tree(1, 1, n);
   for (int i = 1; i <= q; i++)
   {
     cin >> op >> x >> y;
     if (op == 1)
       revise(1, 1, n, x, y);
     else
     {
       cout << calc(1, 1, n, x, y) << endl;
     }
   }
   return 0;
}

从原理到实战带你认识线段树：基础篇

咱们比照一下结构体线段树的用时和内存会发现，数组模仿线段树是优于结构体线段树的，特别是在内存方面

至此，便是线段树的入门篇的悉数内容啦！是不是感觉自己学习到了一个很厉害的新知识而高兴不已呢？

不过先别急着走鸭，学会了新本领，就要找当地练练，否则岂不是白瞎了！

所以，咱们来——

五、写题！我要打写10个！

别被标题吓到了哦，并不是真的有10个题（笑

关于线段树，其实自身并不难，难的是玩出花来。有时候或许会遇到：”我焯？这也能用线段树？“的状况。

所以一定要多写题操练！！

关于写题操练线段树，个人推荐Codeforces渠道的EDU的题单，根本各种常见用法根底题型都有：

从原理到实战带你认识线段树：基础篇

从原理到实战带你认识线段树：基础篇

从原理到实战带你认识线段树：基础篇

（留意看，是part1，part2是区间修正型线段树，现在咱们讲的程度还做不出来，会自闭的）

A – Segment Tree, part 1 – Codeforces

这一题和前面那一题很像，只不过前面的是：给第i个数加上x，而这儿是：把第i个数变成x。

其实便是修正函数的一点点不相同算了，代码如下：

void revise(int k, int l, int r, int x, int y)
{
   if (l == r)
   {
       //这是本来的代码
     //f[k] += y;
    
     //这是现在的代码
     f[k]=y;
     return;
   }
   int mid = (l + r) / 2;
   if (x <= mid)revise(k + k, l, mid, x, y);
   else revise(k + k + 1, mid + 1, r, x, y);
   f[k] = f[k + k] + f[k + k + 1];
}

还有要留意的一点是，前面那一题咱们的规模是1到n，这一题的规模是0到n-1，记得稍加修正。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
​
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
​
#define endl '\n'
#define int ll
#define all(a) a.begin(),a.end()
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;
​
int a[N], f[4 * N];
void build_tree(int k, int l, int r)
{
   if (l == r)
   {
     f[k] = a[l];
     return;
   }
   int mid = (l + r) / 2;
   build_tree(k + k, l, mid);
   build_tree(k + k + 1, mid + 1, r);
   f[k] = f[k + k] + f[k + k + 1];
}
void revise(int k, int l, int r, int x, int y)
{
   if (l == r)
   {
     f[k] = y;
     return;
   }
   int mid = (l + r) / 2;
   if (x <= mid)revise(k + k, l, mid, x, y);
   else revise(k + k + 1, mid + 1, r, x, y);
   f[k] = f[k + k] + f[k + k + 1];
}
int calc(int k, int l, int r, int x, int y)
{
   if (l == x && r == y)return f[k];
   int mid = (l + r) / 2;
   if (y <= mid)return calc(k + k, l, mid, x, y);
   else
     if (x > mid)return calc(k + k + 1, mid + 1, r, x, y);
     else return calc(k + k, l, mid, x, mid) + calc(k + k + 1, mid + 1, r, mid + 1, y);
}
​
signed main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
  
   int n, q, op, x, y;
   cin >> n >> q;
   for (int i = 1; i <= n; i++)cin >> a[i];
   build_tree(1, 1, n);
   for (int i = 1; i <= q; i++)
   {
     cin >> op >> x >> y;
     if (op == 1)
     {
       x++;
       revise(1, 1, n, x, y);
     }
     else
     {
       x++;
       cout << calc(1, 1, n, x, y) << endl;
     }
   }
   return 0;
}

B – Segment Tree, part 1 – Codeforces

这一题中，问的不再是区间和了，而是区间中的最小值。

咱们能够想下，区间和中，父亲节点的值是：左孩子节点的值+右孩子节点的值

现在咱们要的是区间中的最小值，那么只需把父亲节点的值修正成：min(左孩子节点的值，右孩子节点的值) 。即可。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
​
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
​
#define endl '\n'
#define int ll
#define all(a) a.begin(),a.end()
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;
​
int a[N], f[4 * N];
void build_tree(int k, int l, int r)
{
   if (l == r)
   {
     f[k] = a[l];
     return;
   }
   int mid = (l + r) / 2;
   build_tree(k + k, l, mid);
   build_tree(k + k + 1, mid + 1, r);
   //本来的代码
   //f[k] = f[k + k] + f[k + k + 1];
​
   //现在的代码
   f[k] = min(f[k + k], f[k + k + 1]);
}
void revise(int k, int l, int r, int x, int y)
{
   if (l == r)
   {
     f[k] = y;
     return;
   }
   int mid = (l + r) / 2;
   if (x <= mid)revise(k + k, l, mid, x, y);
   else revise(k + k + 1, mid + 1, r, x, y);
   //本来的代码
   //f[k] = f[k + k] + f[k + k + 1];
​
   //现在的代码
   f[k] = min(f[k + k], f[k + k + 1]);
}
int calc(int k, int l, int r, int x, int y)
{
   if (l == x && r == y)return f[k];
   int mid = (l + r) / 2;
   if (y <= mid)return calc(k + k, l, mid, x, y);
   else
     if (x > mid)return calc(k + k + 1, mid + 1, r, x, y);
   //本来的代码
   //else return calc(k + k, l, mid, x, mid) + calc(k + k + 1, mid + 1, r, mid + 1, y);
​
   //现在的代码
     else return min(calc(k + k, l, mid, x, mid), calc(k + k + 1, mid + 1, r, mid + 1, y));
}
​
signed main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
  
   int n, q, op, x, y;
   cin >> n >> q;
   for (int i = 1; i <= n; i++)cin >> a[i];
   build_tree(1, 1, n);
   for (int i = 1; i <= q; i++)
   {
     cin >> op >> x >> y;
     if (op == 1)
     {
       x++;
       revise(1, 1, n, x, y);
     }
     else
     {
       x++;
       cout << calc(1, 1, n, x, y) << endl;
     }
   }
   return 0;
}

C – Segment Tree, part 1 – Codeforces

这一题中，不但需求你求出区间内的最小值，还要求出区间内有多少个这个最小值。

在这一题，咱们能够额定开一个数组cnt。f[i]表明当时区间的最小值是多少，cnt[i]表明当时区间有多少个最小值，很明显的，每个叶子的cnt[i]初始为1。

那么关于父亲节点来说：

  • 假如左孩子和右孩子的最小值相同，父亲节点的最小值便是他们，而父亲节点的cnt，便是两个孩子的cnt加在一起。
  • 假如左孩子的最小值小于右孩子，父亲节点的最小值便是左孩子最小值，父亲节点的cnt便是左孩子的cnt。
  • 假如左孩子的最小值大于右孩子，父亲节点的最小值便是右孩子最小值，父亲节点的cnt便是右孩子的cnt。

在问询操作中，当遇到区间分隔的状况，咱们也要重复如上操作。

为此，这儿我把问询函数的回来值从单个整数改成了一个数对：first是最小值，second是个数cnt。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
​
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
​
#define endl '\n'
#define int ll
#define all(a) a.begin(),a.end()
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;
​
int a[N], f[4 * N], cnt[4 * N];
void build_tree(int k, int l, int r)
{
   if (l == r)
   {
     f[k] = a[l];
     //每个叶子的cnt初始为1
     cnt[k] = 1;
     return;
   }
   int mid = (l + r) / 2;
   build_tree(k + k, l, mid);
   build_tree(k + k + 1, mid + 1, r);
  
   //依据孩子的最小值状况来给父亲节点赋值
   if (f[k + k] == f[k + k + 1])
   {
     f[k] = f[k + k];
     cnt[k] = cnt[k + k] + cnt[k + k + 1];
   }
   else if (f[k + k] < f[k + k + 1])
   {
     f[k] = f[k + k];
     cnt[k] = cnt[k + k];
   }
   else
   {
     f[k] = f[k + k + 1];
     cnt[k] = cnt[k + k + 1];
   }
  
}
void revise(int k, int l, int r, int x, int y)
{
   if (l == r)
   {
     f[k] = y;
     return;
   }
   int mid = (l + r) / 2;
   if (x <= mid)revise(k + k, l, mid, x, y);
   else revise(k + k + 1, mid + 1, r, x, y);
  
   if (f[k + k] == f[k + k + 1])
   {
     f[k] = f[k + k];
     cnt[k] = cnt[k + k] + cnt[k + k + 1];
   }
   else if (f[k + k] < f[k + k + 1])
   {
     f[k] = f[k + k];
     cnt[k] = cnt[k + k];
   }
   else
   {
     f[k] = f[k + k + 1];
     cnt[k] = cnt[k + k + 1];
   }
}
//PII是数对：pair<int,int>
PII calc(int k, int l, int r, int x, int y)
{
    //first是最小值，second是个数
   if (l == x && r == y)return { f[k],cnt[k] };
   int mid = (l + r) / 2;
   if (y <= mid)return calc(k + k, l, mid, x, y);
   else
     if (x > mid)return calc(k + k + 1, mid + 1, r, x, y);
     else
     {
         //当遇到这种区间分隔的状况，咱们也要依据最小值的状况确定答案
       auto i= calc(k + k, l, mid, x, mid);
       auto j = calc(k + k + 1, mid + 1, r, mid + 1, y);
       if (i.first == j.first)
         return { i.first,i.second + j.second };
       else if (i.first < j.first)
         return i;
       else 
         return j;
     }
}
​
signed main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
  
   int n, q, op, x, y;
   cin >> n >> q;
   for (int i = 1; i <= n; i++)cin >> a[i];
   build_tree(1, 1, n);
   for (int i = 1; i <= q; i++)
   {
     cin >> op >> x >> y;
     if (op == 1)
     {
       x++;
       revise(1, 1, n, x, y);
     }
     else
     {
       x++;
       auto t = calc(1, 1, n, x, y);
       cout << t.first << " " << t.second << endl;
     }
   }
   return 0;
}

操练部分取了三道题给大家做解说，这个题单中还有许多其它题等着各位去操练，只需耐性把题都学会，你一定会有所收成！

（你不会真的打算让我讲10题吧，不会吧不会吧）

那么，最终便是咱们的——

六、拜拜了您内

码字不易QAQ，假如各位同学看到这儿，感觉有所收成的话，能否给一个小小的赞支撑一下下，您的支撑便是我的动力。

要是能顺便留下您的评论让我知道对您有收成那我就更高兴啦。

从原理到实战带你认识线段树：基础篇

（期望能被官方推一下吧求求官方哩呜呜呜）

各位再见！假如明天见不到你的话，就祝你早上、中午、晚上都好