一同事公务员上岸了，千辛万苦，终于实现了工资从25000降到5000的飞跃。。。
(关注数据结构和算法，了解更多新知识)
最近一网友发文称自己的同事公务员上岸了，实现了工资从25000降到5000。说实话这个工资降幅还是挺大的，如果是35岁之前成功上岸还是很值得的。
公务员职位虽然稳定，但薪资水平却往往无法与一些高薪的民营企业相提并论。然而，对于这位同事来说，这种转变或许并非完全出于薪资的考虑。毕竟，公务员的职业具有其独特的吸引力，如稳定的职业前景、良好的福利待遇以及相对轻松的工作环境等。或许，对于他来说，这些优势足以弥补薪资上的差距。
我们来看下各位网友的评论，大家更倾向于考公务员，有的网友说了：公务员不能看月薪，要看年终奖。
--------------下面是今天的算法题--------------
今天就不讲LeetCode上的题了，我们来讲一个在LeetCode中经常用到的数据结构：线段树。
假设需要频繁求数组的区间和，我们可能会想到树状数组，或者是前缀和，但如果是求区间的最大值或者区间最小值呢？很明显使用树状数组或者前缀和是无能为力了，但我们可以使用另外一种数据结构-线段树。
线段树是一棵平衡的二叉搜索树，它将每个长度大于 1 的区间划分为左右两个区间递归求解。如果整个区间的长度为 n ，则线段树有 n 个叶子节点，每个叶子节点代表一个单位区间，每个内部节点可以直接获取区间的值（最大值，最小值，区间和等）。
线段树是建立在线段的基础上，每个节点都代表了一条线段 [a,b] ，在叶子节点中 a==b ，对于非叶子节点它的左子节点区间为 [a,(a+b)/2] ，右子节点区间为 [(a+b)/2+1,b] 。我们知道树状数组可以进行区间的修改及查询，但树状数组主要用于区间的求和，功能比较单一，而线段树不光能用于区间的求和，还能用于区间求最大值，最小值，最大公约数等。
能用于线段树的两个子节点的结果必须能合并，比如求和以及求最大值等，区间和=左子节点和+右子节点和，区间最大值= max(左子节点的最大值，右子节点的最大值)。
如果不能合并是没法使用线段树的，比如求众数，左子节点的众数和右子节点的众数可能不是一个，没法合并。这里用求“区间和”为例来介绍线段树，求区间的最大值和最小值原理基本上都一样，这里不在介绍。假设有一个长度为 10 的数组 [1,2,3,4,5,6,7,8,9,10] ，通过他来构建线段树，如下图所示。
我们看到叶子节点都存储的是原数组中的值，非叶子节点存储的是区间的和。在线段树中如果父节点的下标是 i ，他的左右两个子节点的下标分别为 i*2+1 和 i*2+2 。线段树中有两个数组，一个是原数组，一个是线段树数组。
int[] nums;// 原数组。int[] trees;// 线段树数组，长度是原数组长度的4倍。构建线段树
线段树是一棵平衡的二叉搜索树，构建的时候可以使用递归的方式构建。
// 调用方式 build(0, 0, nums.length - 1);
// 调用之前要先初始化nums和trees数组。
void build(int root, int left, int right) {
if (left == right) {// 到叶子节点，直接对线段树数组赋值。
trees[root] = nums[left];
} else {
// 递归构建左子树和右子树。
int mid = (left + right) >>> 1;
build(root * 2 + 1, left, mid);
build(root * 2 + 2, mid + 1, right);
// 类似于二叉树的后续遍历，子节点计算完之后在计算当前节点。
pushUp(root);
}
}
// 往上推。
void pushUp(int i) {
// 求区间和，父节点的值等于左右子节点之和。
trees[i] = trees[i * 2 + 1] + trees[i * 2 + 2];
// 如果是求区间最大值可以这样写。
// trees[i] = Math.max(trees[i * 2 + 1], trees[i * 2 + 2]);
}
单点查询
单点查询是从线段树的根节点开始往下查询，直到叶子节点，最后叶子节点的值就是我们要查找的结果。
// 单点查询。
int querySingle(int pos) {
if (pos < 0 || pos >= nums.length)
return -1;
return querySingleHelper(0, 0, nums.length - 1, pos);
}
/**
* @param root 当前节点
* @param start 当前节点的左区间
* @param end 当前节点的右区间
* @param pos 要查询的值
* @return
*/
int querySingleHelper(int root, int start, int end, int pos) {
if (start == end)// 到叶子节点直接返回。
return trees[root];
int mid = (start + end) >>> 1;
if (pos <= mid)// 在左子节点查找。
return querySingleHelper(root * 2 + 1, start, mid, pos);
// 在右子节点查找。
return querySingleHelper(root * 2 + 2, mid + 1, end, pos);
}
单点修改
单点修改和单点查询类似，他是先找到叶子节点，最后在进行修改，修改完之后父节点值也会发生变动，所以还需要往上推，更改父节点的值，一直到根节点，如下图所示。
我们看到子节点的值改了，父节点的值都要跟着改变。
// 单点更新，nums[pos]+=val
void updateSingle(int pos, int val) {
if (pos < 0 || pos >= nums.length)
return;
updateSingleHelper(0, 0, nums.length - 1, pos, val);
}
void updateSingleHelper(int root, int start, int end, int pos, int val) {
if (start == end) {// 已经到叶子节点了，直接更新。
trees[root] += val;// 这里是相对值，是加，不是直接赋值。
} else {
int mid = (start + end) >>> 1;
if (pos <= mid)// 目标位置在左边。
updateSingleHelper(root * 2 + 1, start, mid, pos, val);
else// 目标位置在右边。
updateSingleHelper(root * 2 + 2, mid + 1, end, pos, val);
pushUp(root);// 往上推，更新父节点的值。
}
}
// 区间查询。
int queryRange(int left, int right) {
return queryRangeHelper(0, 0, nums.length - 1, left, right);
}
int queryRangeHelper(int root, int start, int end, int left, int right) {
// 当前节点在查找的区间之内，直接返回该节点的值。
if (left <= start && right >= end)
return trees[root];
int mid = (start + end) >>> 1;
int sum = 0;
if (left <= mid)// 在左边查找。
sum += queryRangeHelper(root * 2 + 1, start, mid, left, right);
if (right > mid)// 在右边查找，注意这里没有else，因为查找区间可能两边都有。
sum += queryRangeHelper(root * 2 + 2, mid + 1, end, left, right);
return sum;
}
// 区间修改，把区间[left,right]中所有的数字加上val。
void updateRange(int left, int right, int val) {
updateRangeHelper(0, 0, nums.length - 1, left, right, val);
}
void updateRangeHelper(int root, int start, int end, int left,
int right, int val) {
if (start == end) {
trees[root] += val;// 到叶子节点，值加上val。
} else {
int mid = (start + end) / 2;
if (left <= mid)// 在左子节点修改。
updateRangeHelper(root * 2 + 1, start, mid, left, right, val);
if (right > mid)// 在右子节点修改，和查询一样，也是没有 else。
updateRangeHelper(root * 2 + 2, mid + 1, end, left, right, val);
pushUp(root);// 往上推，更新父节点的值。
}
}
我们看到区间修改的时候他会把每一个叶子节点都要修改，然后在往上更新父节点，实际上可以不这样做，如果某个子树的值全部要修改，只需要更改这棵子树的根节点即可，给他加个标记，然后这棵子树的子节点都不要修改了。就像过年别人给你压岁钱一样，这个钱不是直接给你，而是先给你妈，然后你妈在给你们。由于给的人太多（类似于区间的频繁修改），你妈说这个钱就不一一发给你们了，放我这保管，需要的时候在给你们。
假设我们需要给区间 [3,9] 中的所有节点都加上 10 ，当我们找到需要更新的节点区间 [3,4] 和 [5,9] 的时候，只需要修改他们的值就可以了，然后给他加个懒标记值，他们的子节点就不在修改了，但他们的父节点还是要更新，如下图所示。
int[] nums;// 原数组。int[] trees;// 线段树数组。int[] lazy;// 懒标记数组。/**
* 懒标记下发
*
* @param index 当前节点
* @param lCount 当前节点左子节点的个数
* @param rCount 当前节点右子节点的个数
*/
void pushDown(int index, int lCount, int rCount) {
if (lazy[index] != 0) {// 懒标记不为0开始处理。
trees[index * 2 + 1] += lCount * lazy[index];// 更新左子节点的值。
trees[index * 2 + 2] += rCount * lazy[index];// 更新右子节点的值。
lazy[index * 2 + 1] += lazy[index];// 左子节点懒标记累加。
lazy[index * 2 + 2] += lazy[index];// 右子节点懒标记累加。
lazy[index] = 0;//当前节点的懒标记清空。
}
}
void updateRangeHelper(int root, int start, int end, int left, int right,
int val) {
if (left <= start && right >= end) {// 当前节点全部被更新区域覆盖。
trees[root] += val * (end - start + 1);// val*子节点的个数。
lazy[root] += val;// 当前节点要加上懒标记。
} else {
int mid = (start + end) / 2;
// 当前节点没有全部被[left, right]覆盖，说明只更新当前子树
// 的一部分，需要把懒标记下发到当前节点的两个子节点中。
pushDown(root, mid - start + 1, end - mid);
if (left <= mid)// 在左子节点修改。
updateRangeHelper(root * 2 + 1, start, mid, left, right, val);
if (right > mid)// 在右子节点修改，和查询一样，也是没有 else。
updateRangeHelper(root * 2 + 2, mid + 1, end, left, right, val);
pushUp(root);// 往上推，更新父节点的值。
}
}
int queryRangeHelper(int root, int start, int end, int left, int right) {
// 当前节点在查找的区间之内，直接返回该节点的值。
if (left <= start && right >= end)
return trees[root];
int mid = (start + end) >>> 1;
// 查找区域没有把当前节点的区域覆盖，说明会到子节点中
// 查找，需要把当前节点的懒标记下发到子节点中。
pushDown(root, mid - start + 1, end - mid);
int sum = 0;
if (left <= mid)// 在左边查找。
sum += queryRangeHelper(root * 2 + 1, start, mid, left, right);
if (right > mid)// 在右边查找，注意这里没有else，因为查找区间可能两边都有。
sum += queryRangeHelper(root * 2 + 2, mid + 1, end, left, right);
return sum;
}