package SegmentTree
import (
"encoding/json"
"math"
"math/rand"
"reflect"
"sort"
"testing"
"time"
)
//线段树 区间求和、区间最大值，区间最小值（Range Minimum/Maximum Query problem）或者区间异或值的查询
// 区间的更新，修改，查询，一些东西，怎么比较快
/*
数组：[3,2,4,6,......]
0.... 1000
做一个结构，线段树结构
add(L, R, V, Arr) // L..R 所有数字加一个V
update(L, R, V, Arr) // L..R 所有数字变成V
getSum(L, R, Arr) // 返回L..R上的累加和
如何做到三个方法比较快 达到O(LogN)水平
最早解决线段重合问题
概念建立
假设数组长度是2的某次方
假如是 8
arr [ ]
1 8
二分建立信息
1~8
1~4 5~8
1~2 3~4 5~6 6~7
1 2 3 4 5 6 7 8
任何一个点的信息可以由于左右两个孩子生成 想要收集所有信息， 需要2 * 8 -1 个空间
不管N多大，都希望构建出一棵满二叉树
len arr = 6
可以认为最底层还是8个节点，认为第7个数，第8个数都是0， 然后往上构建，知道实际数量， 对结果无影响
满二叉树：大范围上，从左往右，每一次都均分下去，所以，构建一棵满二叉树
给定一个任意长度N，需要准备多大空间，能把所有的想表达的信息都装下。 4倍
N正好是2的某次方的时候，2倍就够用
如: N = 5
1 2 3 4 5
18
14 58
12 34 56 78
1 2 3 4 5 0 0 0
*/
/*
arr [3, 2, 5, 7]
1 2 3 4
17(1~4)
5(1~2) 12(3~4)
3(1,1) 2(2~2) 5(3~3) 7(4~4)
sum [x, 17, 5, 12, 3, 2, 5 7]
0 1 2 3 4 5 6 7
怎么找到具体范围对应的下标是什么？
最大的范围对应1下标
2~2范围？
来自左孩子范围：1~2 左孩子下标 2*i 右孩子下标 2*i + 1
懒更新 1 ~ 6 范围上加 4
收到过一个任务，不彻底下发到底，存在lazy数组里 代价O(logN)
*/
type SegmentTree struct {
MaxN int
arr []int // arr[]为原序列的信息从0开始，但在arr里是从1开始的
sum []int // sum[]模拟线段树维护区间和
lazy []int // lazy[]为累加和懒惰标记
change []int // change[]为更新的值
update []bool // update[]为更新慵懒标记
}
func NewSegmentTreeWithArray(origin []int) *SegmentTree {
MaxN := len(origin) + 1
arr := make([]int, MaxN) // arr[0]不用, 从arr[1]开始使用
for i := 1; i < MaxN; i++ {
arr[i] = origin[i-1]
}
sum := make([]int, MaxN<<2) // 用来支持脑补概念中，某一个范围的累加和信息
lazy := make([]int, MaxN<<2) // 用来支持脑补概念中，某一个范围沒有往下传递的累加任务
change := make([]int, MaxN<<2) // 用来支持脑补概念中，某一个范围有没有更新操作的任务
update := make([]bool, MaxN<<2) // 用来支持脑补概念中，某一个范围更新任务，更新成了什么
return &SegmentTree{
MaxN: MaxN,
arr: arr,
sum: sum,
lazy: lazy,
change: change,
update: update,
}
}
// 在初始化阶段，先把sum数组，填好
// 在arr[l~r]范围上，去build，1~N，
// rt : 这个范围在sum中的下标
func (st *SegmentTree) build(l, r, rt int) { //使用时先build 比如：1~4 (l,r)上的数, 到哪个(rt)下标上找
if l == r { // 范围上只有一个数
st.sum[rt] = st.arr[l]
return
}
// 范围上不只一个数
mid := (l + r) >> 1 // 往下分
st.build(l, mid, rt<<1) // 左侧 i * 2
st.build(mid+1, r, rt<<1|1) // 右侧 i * 2 + 1
st.pushUp(rt) // 汇总
}
func (st *SegmentTree) pushUp(rt int) {
st.sum[rt] = st.sum[rt<<1] + st.sum[rt<<1|1] // 2 * i 位置 和 2 * i + 1位置
}
// 之前的，所有懒增加，和懒更新，从父范围，发给左右两个子范围
// 分发策略是什么
// ln表示左子树元素结点个数，rn表示右子树结点个数
func (st *SegmentTree) pushDown(rt, ln, rn int) {
if st.update[rt] {
st.update[rt<<1] = true
st.update[rt<<1|1] = true
st.change[rt<<1] = st.change[rt]
st.change[rt<<1|1] = st.change[rt]
st.lazy[rt<<1] = 0
st.lazy[rt<<1|1] = 0
st.sum[rt<<1] = st.change[rt] * ln
st.sum[rt<<1|1] = st.change[rt] * rn
st.update[rt] = false
}
if st.lazy[rt] != 0 {
st.lazy[rt<<1] += st.lazy[rt]
st.sum[rt<<1] += st.lazy[rt] * ln
st.lazy[rt<<1|1] += st.lazy[rt]
st.sum[rt<<1|1] += st.lazy[rt] * rn
st.lazy[rt] = 0
}
}
// L~R 所有的值变成C
// l~r rt
func (st *SegmentTree) UPDATE(L, R, C, l, r, rt int) {
if L <= l && r <= R {
st.update[rt] = true
st.change[rt] = C
st.sum[rt] = C * (r - l + 1)
st.lazy[rt] = 0
return
}
// 当前任务躲不掉，无法懒更新，要往下发
mid := (l + r) >> 1
st.pushDown(rt, mid-l+1, r-mid)
if L <= mid {
st.UPDATE(L, R, C, l, mid, rt<<1)
}
if R > mid {
st.UPDATE(L, R, C, mid+1, r, rt<<1|1)
}
st.pushUp(rt)
}
// L~R, C 任务！
// rt，l~r
func (sg *SegmentTree) add(L, R, C, l, r, rt int) {
// 任务如果把此时的范围全包了！
if L <= l && r <= R {
sg.sum[rt] += C * (r - l + 1)
sg.lazy[rt] += C
return
}
// 任务没有把你全包！
// l r mid = (l+r)/2
mid := (l + r) >> 1
sg.pushDown(rt, mid-l+1, r-mid)
// L~R
if L <= mid {
sg.add(L, R, C, l, mid, rt<<1)
}
if R > mid {
sg.add(L, R, C, mid+1, r, rt<<1|1)
}
sg.pushUp(rt)
}
// 1~6 累加和是多少？ 1~8 rt
func (sg *SegmentTree) query(L, R, l, r, rt int) int {
if L <= l && r <= R {
return sg.sum[rt]
}
mid := (l + r) >> 1
sg.pushDown(rt, mid-l+1, r-mid)
ans := 0
if L <= mid {
ans += sg.query(L, R, l, mid, rt<<1)
}
if R > mid {
ans += sg.query(L, R, mid+1, r, rt<<1|1)
}
return ans
}
type Right struct {
arr []int
}
func NewRight(origin []int) *Right {
arr := make([]int, len(origin)+1)
for i := 0; i < len(origin); i++ {
arr[i+1] = origin[i]
}
return &Right{arr}
}
func (r *Right) update(L, R, C int) {
for i := L; i <= R; i++ {
r.arr[i] = C
}
}
func (r *Right) add(L, R, C int) {
for i := L; i <= R; i++ {
r.arr[i] += C
}
}
func (r *Right) query(L, R int) int {
ans := 0
for i := L; i <= R; i++ {
ans += r.arr[i]
}
return ans
}
func generateRandomArray(len, max int) []int {
rand.Seed(time.Now().UnixNano())
size := rand.Int()%len + 1
origin := make([]int, size)
for i := 0; i < size; i++ {
origin[i] = rand.Int()%max - rand.Int()%max
}
return origin
}
func test() bool {
length := 100
max := 1000
testTimes := 5000
addOrUpdateTimes := 1000
queryTimes := 500
for i := 0; i < testTimes; i++ {
origin := generateRandomArray(length, max)
origin1 := make([]int, len(origin))
for j := 0; j < len(origin); j++ {
origin1[j] = origin[j]
}
seg := NewSegmentTreeWithArray(origin)
S := 1
N := len(origin)
root := 1
seg.build(S, N, root)
rig := NewRight(origin1)
rand.Seed(time.Now().UnixNano())
for j := 0; j < addOrUpdateTimes; j++ {
num1 := rand.Int()%N + 1
num2 := rand.Int()%N + 1
L := Min(num1, num2)
R := Max(num1, num2)
C := rand.Int()%max - rand.Int()%max
if rand.Int()%100 < 50 {
seg.add(L, R, C, S, N, root)
rig.add(L, R, C)
} else {
seg.UPDATE(L, R, C, S, N, root)
rig.update(L, R, C)
}
}
for k := 0; k < queryTimes; k++ {
num1 := rand.Int()%N + 1
num2 := rand.Int()%N + 1
L := Min(num1, num2)
R := Max(num1, num2)
ans1 := seg.query(L, R, S, N, root)
ans2 := rig.query(L, R)
if !reflect.DeepEqual(ans1, ans2) {
return false
}
}
}
return true
}
func Max(a, b int) int {
if a < b {
return b
}
return a
}
func Min(a, b int) int {
if a > b {
return b
}
return a
}
func TestSegmentTree(t *testing.T) {
origin := []int{2, 1, 1, 2, 3, 4, 5}
seg := NewSegmentTreeWithArray(origin)
S := 1 // 整个区间的开始位置，规定从1开始，不从0开始 -> 固定
N := len(origin) // 整个区间的结束位置，规定能到N，不是N-1 -> 固定
root := 1 // 整棵树的头节点位置，规定是1，不是0 -> 固定
L := 2 // 操作区间的开始位置 -> 可变
R := 5 // 操作区间的结束位置 -> 可变
C := 4 // 要加的数字或者要更新的数字 -> 可变
// 区间生成，必须在[S,N]整个范围上build
seg.build(S, N, root)
// 区间修改，可以改变L、R和C的值，其他值不可改变
seg.add(L, R, C, S, N, root)
// 区间更新，可以改变L、R和C的值，其他值不可改变
seg.UPDATE(L, R, C, S, N, root)
// 区间查询，可以改变L和R的值，其他值不可改变
sum := seg.query(L, R, S, N, root)
t.Log(sum)
t.Log("对数器测试开始...")
if test() {
t.Log("通过")
} else {
t.Log("未通过")
}
}
/*
线段树实例1
给定一个数组arr，用户希望你实现如下三个方法
1. void add(int L, int R, int V ):让数组arr[L..R]上每个数都加上V
2. void update(int L, int R, int V): 让数组arr[L..R]上每个数都变成V
3. int sum(int L, int R): 返回arr[L..R]这个范围的整体累加和
怎么让这三个方法，时间复杂度都是O(logN)
*/
/*
题目
https://leetcode-cn.com/problems/falling-squares/
线段树实例2
想象一下标准的俄罗斯方块游戏，X轴是积木最终下落到底的轴线
下面是这个游戏的简化版：
1.只会下落正方形积木
2.[a,b] -> 代表一个边长为b的正方形积木，积木左边缘沿着X = a 这条线从上方掉落
3.认为真个X轴都可以接住积木，也就是说简化版游戏是没有整体的左右边界的
4.没有整体的左右边界，所以简化版游戏不会消除积木，因为不会右哪一层被填满。
给定一个N * 2 的二维数组matrix，可以代表N个积木依次掉落
返回每一次调货之后的最大高度
*/
type segmentTree struct {
max []int
change []int
update []bool
}
func NewsegmentTree(size int) *segmentTree {
N := size + 1
return &segmentTree{
max: make([]int, N<<2),
change: make([]int, N<<2),
update: make([]bool, N<<2),
}
}
func (seg *segmentTree) pushUp(rt int) {
seg.max[rt] = Max(seg.max[rt<<1], seg.max[rt<<1|1])
}
// ln表示左子树元素结点个数，rn表示右子树结点个数
func (seg *segmentTree) pushDown(rt, ln, rn int) {
if !seg.update[rt] {
return
}
seg.update[rt<<1] = true
seg.update[rt<<1|1] = true
seg.change[rt<<1] = seg.change[rt]
seg.change[rt<<1|1] = seg.change[rt]
seg.max[rt<<1] = seg.change[rt]
seg.max[rt<<1|1] = seg.change[rt]
seg.update[rt] = false
}
func (seg *segmentTree) Update(L, R, C, l, r, rt int) {
if L <= l && r <= R {
seg.update[rt] = true
seg.change[rt] = C
seg.max[rt] = C
return
}
mid := (l + r) >> 1
seg.pushDown(rt, mid-l+1, r-mid)
if L <= mid {
seg.Update(L, R, C, l, mid, rt << 1)
}
if R > mid {
seg.Update(L, R, C, mid+1, r, rt<<1|1)
}
seg.pushUp(rt)
}
func (seg *segmentTree) query(L, R, l, r, rt int) int {
if L <= l && r <= R {
return seg.max[rt]
}
mid := (l + r) >> 1
seg.pushDown(rt, mid-l+1, r-mid)
left := 0
right := 0
if L <= mid {
left = seg.query(L, R, l, mid, rt << 1)
}
if R > mid {
right = seg.query(L, R, mid+1, r, rt << 1 | 1)
}
return Max(left, right)
}
func index(positions [][]int) map[int] int {
pos := make(map[int]bool)
for _, arr := range positions {
pos[arr[0]] = true
pos[arr[0] + arr[1] - 1] = true
}
tmp := make([]int,len(pos))
index := 0
for key, _ := range pos {
tmp[index] = key
index++
}
sort.Ints(tmp)
mp := make(map[int]int)
count := 0
for _, value := range tmp {
count++
mp[value] = count
}
return mp
}
//https://leetcode-cn.com/problems/falling-squares/
func fallingSquares(positions [][]int) []int {
mp := index(positions)
N := len(mp)
seg := NewsegmentTree(N)
max := 0
res := make([]int,0)
// 每落一个正方形，收集一下，所有东西组成的图像，最高高度是什么
for _, arr := range positions {
L := mp[arr[0]]
R := mp[arr[0] + arr[1] - 1]
height := seg.query(L,R,1,N,1) + arr[1]
max = Max(max, height)
res = append(res, max)
seg.Update(L,R,height,1,N,1)
}
return res
}
func TestSeg(t *testing.T) {
t.Log(fallingSquares([][]int{{1,2},{2,3},{6,1}}))
}
/*
扩展
有 1 到 N个房子， 有17种颜色，从L..R刷成一种颜色，查询任何L..R颜色有多少种
*/
/*
线段重合问题，哪一段线段盖的东西是最多的，线段树可以解，但是太重了
[1,3] [2,6] [4, 9]
|----------------------|
|----------------|
|-------|
|---|---|---|---|---|---|---|---|---|---|---> X
0 1 2 3 4 5 6 7 8 9
解法
1.根据线段开始位置的值排序
[4,6], [1,10], [2,5], [1,7]
[1,10], [1,7], [2,5],[4,6]
2.一个线段一个线段的处理，线段开始位置越早，越先处理
3.准备一个堆(小根堆)，堆里放
[1,10] <= 1 的弹出 把10 放进去
求一个答案， 1 也就是 堆的size
[1,7] 堆中 放入 7
求一个答案 2
...
求N个答案，最大值就是最终答案
*/
func maxCover1(lines [][] int) int { // 用0.5检测正好接壤
min := math.MaxInt
max := math.MinInt
for i := 0; i < len(lines); i++ {
min = Min(min,lines[i][0])
max = Max(max,lines[i][1])
}
cover := 0
for p := float64(min) + 0.5; p < float64(max); p += 1.0 {
cur := 0
for i := 0; i < len(lines); i++ {
if float64(lines[i][0]) < p && float64(lines[i][1]) > p {
cur++
}
}
cover = Max(cover,cur)
}
return cover
}
type Line struct {
start, end int
}
func maxCover2(m [][] int) int {
lines := make([]Line,len(m))
for i := 0; i < len(m); i++ {
lines[i] = Line{m[i][0],m[i][1]}
}
sort.Slice(lines, func(i, j int) bool {
return lines[i].start < lines[j].start
})
heap := NewMyHeap(func(a, b interface{}) bool {
return a.(Line).start < b.(Line).start
})
max := 0
for i := 0; i < len(lines); i++ {
for !heap.IsEmpty() && heap.Peek().(Line).end <= lines[i].start {
heap.pop()
}
heap.push(lines[i])
max = Max(max,heap.heapSize)
}
return max
}
func TestCover(t *testing.T) {
arr := [][]int{{1,10}, {1,7}, {2,5},{4,6},{2,10}}
t.Log(maxCover1(arr) == maxCover2(arr))
t.Log(maxCover1(arr),maxCover2(arr))
}
type MyHeap struct {
heap []interface{}
indexMap map[interface{}]int //任何一个样本，记录在堆上的位置
heapSize int
comparator func(a, b interface{}) bool //比大小
}
func (my *MyHeap)String() string {
byt,_ := json.MarshalIndent(my.heap,"\t"," ")
return string(byt)
}
func NewMyHeap(com func(a, b interface{}) bool ) *MyHeap {
return &MyHeap{
heap: []interface{}{},
indexMap: map[interface{}]int{},
heapSize: 0,
comparator: com,
}
}
func (my *MyHeap) IsEmpty() bool {
return my.heapSize == 0
}
func (my *MyHeap) Size() int {
return my.heapSize
}
func (my *MyHeap)contains(key interface{}) bool {
_, ok := my.indexMap[key]
return ok
}
func (my *MyHeap)push(value interface{}) {
my.heap = append(my.heap, value)
my.indexMap[value] = my.heapSize
my.heapInsert(my.heapSize)
my.heapSize++
}
func (my *MyHeap)pop() interface{} {
ans := my.heap[0]
end := my.heapSize - 1
my.swap(0,end)
my.heap = my.heap[0:end]
delete(my.indexMap,ans)
my.heapSize--
my.heapify(0,my.heapSize)
return ans
}
func (my *MyHeap)Peek() interface{} {
return my.heap[0]
}
func (my *MyHeap)heapInsert(index int){
for my.comparator(my.heap[index],my.heap[(index -1) /2]) {
my.swap(index,(index - 1) / 2)
index = (index - 1) / 2
}
}
func (my *MyHeap)resign(val interface{}) {
valueIndex := my.indexMap[val]
my.heapInsert(valueIndex) //上行或下行，两个分支 只会中一个
my.heapify(valueIndex,my.heapSize) //都不中就出去，可以实现重复加入值，按引用传递的话
}
func (my *MyHeap)heapify(index, heapSize int) {
leftChild := 2 * index + 1
for leftChild < heapSize {
best := leftChild //下沉
if leftChild + 1 < heapSize && my.comparator(my.heap[best + 1], my.heap[best]) {
best = leftChild + 1
}
if !my.comparator(my.heap[best],my.heap[index]) {
break
}
my.swap(index,best)
index = best
leftChild = 2 *index + 1
}
}
func (my *MyHeap)swap(i, j int) { //强同步
my.heap[i], my.heap[j] = my.heap[j],my.heap[i]
my.indexMap[my.heap[i]],my.indexMap[my.heap[j]] = my.indexMap[my.heap[j]],my.indexMap[my.heap[i]]
}
/*
给你一些矩阵，给你 左上角的点和右下角的点 [1,3,2,6]
|
|
|
|
|
|
| ------
| | --|----
| | | | |
| ---|-- |
----------------------------------------------------------------
|
|
|
|
|
|
|
|
|
返回哪个区域矩形盖的最多，返回数量即可
按照底的从小达到顺序遍历
准备一个list，其中放的是矩形
任何多个矩形，公共区域的底必是某一个矩形的底
---------
| |
| |
| ----|---
| ||||| |
--------- |
| |
--------
*/
// todo 未测试
type Rectangle struct {
up, down, left, right int
}
func maxCover(recs []Rectangle) int {
if recs == nil || len(recs) == 0 {
return 0
}
// 根据 down （底）排序
sort.Slice(recs, func(i, j int) bool {
return recs[i].down < recs[j].down
})
// 可能会对当前底边的公共区域产生影响的矩形
leftOrdered := NewMyHeap(func(a, b interface{}) bool {
return a.(Rectangle).left < b.(Rectangle).left // 根据left 排序
})
ans := 0
for i := 0; i < len(recs); i++ { // 依次考察每一个矩形的底边
curDown := recs[i].down// 当前底边的值取出来
index := i
for recs[index].down == curDown {
if leftOrdered.contains(recs[index]) {
leftOrdered.resign(recs[index])
}else {
leftOrdered.push(recs[index]) // O(logN)
}
index++
}
i = index
// O(N)
removeLowerOnCurDown(leftOrdered,curDown)
rightOrdered := NewMyHeap(func(a, b interface{}) bool {
return a.(Rectangle).right < b.(Rectangle).right // 根据left 排序
})
for !leftOrdered.IsEmpty() {
rec := leftOrdered.pop().(Rectangle)
removeLeftOnCurLeft(rightOrdered,rec.left)
if rightOrdered.contains(rec) {
rightOrdered.resign(rec)
}else {
rightOrdered.push(rec)
}
ans = Max(ans,rightOrdered.heapSize)
}
}
return ans
}
func removeLeftOnCurLeft(heap *MyHeap, curDown int) {
arr := make([]Rectangle,0)
for !heap.IsEmpty() {
if rec := heap.pop().(Rectangle);rec.up > curDown {
arr = append(arr,rec)
}
}
for k := range arr {
heap.push(arr[k])
}
}
func removeLowerOnCurDown(heap *MyHeap, curDown int) {
arr := make([]Rectangle,0)
for !heap.IsEmpty() {
if rec := heap.pop().(Rectangle); rec.right <= curDown {
arr = append(arr,rec)
}else {
break
}
}
for k := range arr {
heap.push(arr[k])
}
}
func TestMaxCover(t *testing.T) {
t.Log(maxCover([]Rectangle{{2,1,0,1},{2,2,1,1}}))
}