segmenttree

TODO

线段树

线段树是一种数据结构，主要用来解答区间查询问题，对于满足区间可加性的问题基本都可以维护，常见的维护如下。

区间和
区间最值和出现的次数
区间gcd/lcm
区间为0的个数，以及第k个0的位置
查询前项和不小于某个数的第一个位置，带更新
- 朴素做法是二分位置，然后线段树维护，复杂度O(logn*logn)
- 另一种做法是充分利用线段树性质，因为前项和是递增的，复杂度O(logn)
查询区间第一个比x大的数
- 朴素做法二分区间右端点，然后线段树维护，复杂度O(logn*logn)
- 类似于上面，因为max和前项和类似，都是递增的，可以丰富利用线段树性质，复杂度O(logn)
查询区间最大的子序列和

题目选讲

你能回答这些问题吗 ⭐⭐⭐
- 题意：给出n个数，和m个操作，一个操作是问l到r区间最大的连续字段和是多少，另一个操作是单点修改。
- 题解：使用线段数维护区间的sum，lmax，rmax，max。那么p.sum = l.sum + r.sum, p.lmax = max(l.lmax, l.sum + r.lmax), p.rmax = max(r.rmax, r.sum + l.rmax), p.max = max(max(l.max, r.max), l.rmax + r.lmax)。画一下线段树图，很容易理解。
- 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/CH4301.cpp
Colonial Mansions：https://codeforces.com/gym/101962/problem/I ⭐⭐⭐⭐
- 题意：给n个房屋，高度是h[]，第i个房屋可以去第i-1和第i+1个房屋，单点修改房屋高度，查询操作，输入i，h，问第i个房屋可以去那些房屋（满足相邻的房屋高度差小于h即可去)
- 题解：线段树维护差分序列，对于查询操作其实就是问从i房屋向左向右序列一直小于等于h的个数。我们可以维护差分序列的区间最大值，然后二分查找向左向右扩展的距离。
- 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/cf101962I.cpp
Danil and a Part-time Job：https://codeforces.com/contest/877/problem/E ⭐⭐⭐⭐
- 题意：给一颗树，树上每个节点为0或者1，两种操作，更新x：x以及x的子节点取反，查询x：x以及x的子节点中1的个数。
- 题解：首先因为是字数操作，所以先取到dfs序，这样子树操作就变成的区间维护取反，使用线段树维护1的个数和0的个数，那么每次取反就是1的个数和0的个数交换，因为要区间更新，需要lazy propagation。
- 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/cf877E.cpp
Serge and Dining Room：https://codeforces.com/contest/1179/problem/C ⭐⭐⭐⭐⭐
- 题意：给出n个物品，每个物品价值a[i]，给出m个人，每个人有b[i]块钱，每个人只能买一个物品，每个物品只能被一个人买，从钱多的人开始买，每个人买物品的时候，会选择当前可以买的物品里价值最大的。问所有人都买过物品后，剩余价值最大的物品是多少。单点修改，可以修改某个物品的价值，或者某个人所有的钱。
- 题解：因为所有的价值一共1e6，所以可以预处理出数组c，数组的下标表示价值，数组的值表示有i块钱的人-价值为i的物品个数，那么假设没有查询的话，就是从1e6开始枚举计算前向和，遇到第一个前项和<0的时候，说明那个价值的物品没法被买(拥有>=i块钱的人小于价值>=i的物品)。那么我们可以用线段树维护这个前项和，来完成修改和查询，原来的单点修改这里变成了区间修改。对于查询区间第一个<0的下标的方式是因为维护的是权值线段树，同时每个节点维护最小值就ok，如果当前线段最小值>=0，那么直接return不用继续找了，复杂度是O(logn)
- 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/cf1179C.cpp
Reflection：https://codeforces.com/gym/101992/problem/L ⭐⭐⭐⭐⭐
- 题意：直角坐标系给一个y=x的直线，现在每次操作可以对某个点做以这个点的水平直线的镜面反射，以及查询某个点的y值
- 题解：维护相邻两个点的差值，要么是1要么是-1，每次操作，相当于这个差值取反，每个点的y值相当于0到这个点的差值和。线段树维护即可
- 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/cf101992L.cpp
Subarray Sorting：https://codeforces.com/contest/1187/problem/D ⭐⭐⭐⭐⭐
- 题意：给两个数组，问数组b是否可以由数组a通过任意个区间sort操作变换得到。
- 题解：我们考虑那些情况会导致失败，对于数组b的每一个数，如果数组a中这个数前面的数有比这个数小的，那说明有问题每次排除一个旧把那个值置为最大值。用线段树维护就好。
- 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/BlueBook/cf101992L.cpp

Success is like being pregnant, everybody congratulates you, but nobody knows how many times your were fucked before you got there.

Prepare my interview!

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

segmenttree

TODO

线段树

题目选讲

Clone this wiki locally