# Posts tagged as “segment tree”

You are given an integer array nums and an integer k.

Find the longest subsequence of nums that meets the following requirements:

• The subsequence is strictly increasing and
• The difference between adjacent elements in the subsequence is at most k.

Return the length of the longest subsequence that meets the requirements.

subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5
Explanation:
The longest subsequence that meets the requirements is [1,3,4,5,8].
The subsequence has a length of 5, so we return 5.
Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.


Example 2:

Input: nums = [7,4,5,1,8,12,4,7], k = 5
Output: 4
Explanation:
The longest subsequence that meets the requirements is [4,5,8,12].
The subsequence has a length of 4, so we return 4.


Example 3:

Input: nums = [1,5], k = 1
Output: 1
Explanation:
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.


Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i], k <= 105

## Solution: DP + Segment Tree | Max range query

Let dp[i] := length of LIS end with number i.
dp[i] = 1 + max(dp[i-k:i])

Naive dp takes O(n*k) time which will cause TLE.

We can use segment tree to speed up the max range query to log(m), where m is the max value of the array.

Time complexity: O(n*logm)
Space complexity: O(m)

## C++

Segment tree is a balanced binary tree with O(logn) height given n input segments.
Segment tree supports fast range query O(logn + k), and update O(logn).
Building such a tree takes O(n) time if the input is an array of numbers.

Tree之所以大行其道就是因为其结构和人类组织结构非常接近。就拿公司来说好了，CEO统领全局(root)，下面CTO，CFO等各自管理一个部门，每个部门下面又正好有好两个VP，每个VP下面又有两个director，每个director下面又有2个manager，每个manager下面又有2个底层员工(leaf)，为什么是2？因为我们用二叉树啊~

nums = [1, 3, 5]，
sumRange(0, 2) = 1+3+5 = 9
update(1, 2) => [1, 2, 5]
sumRange(0, 2) = 1 + 2 + 5 = 7

sumRange(i, j) := sums[j] – sums[i – 1] if i > 0 else sums[j]

Update: O(logn)，Query: O(logn+k)

root存储的是所有元素的和。

start #起始范围
end #终止范围
mid #拆分点，通常是 (start + end) // 2
val #所有子元素的和
left #左子树
right #右子树

Update: 由于每次只更新一个元素的值，所以CEO知道这个员工是哪个人管的，派发下去就行了，然后把新的结果再返回回来。

T(n) = T(n/2) + 1 => O(logn)

Query: query的range可以是任意的，就有以下三种情况：

case 1: 这个range正好和我负责的range完全相同。比如sumQuery(CTO, 0, 99)，这个时候CTO直接返回已经求解过的所有下属的和即可。

case 2: 这个range只由我其中一个下属负责。比如sumQuery(CEO, 0, 10)，CEO知道0~10全部由CFO负责，那么他就直接返回sumQuery(CTO, 0, 10)。

case 3: 这个range覆盖了我的两个下属，那么我就需要调用2次。比如sumQuery(CEO, 80, 120)，CEO知道0~99由CTO管，100~199由CFO管，所以他只需要返回：

sumQuery(CTO, 80, 99) + sumQuery(CFO, 100, 120)

Query需要访问到的节点数量的worst和average case。Worst case 大约访问 4*logn – 3 个节点，这个数字远远小于n。和n成对数关系。

CEO管200人，那么就找2个人(CTO，CFO各管100人。CTO管100人，再找2个VP各管50人，以此类推，直到manager管2个人，2个人都是底层员工(leaf)，没有人管（双关）。

CEO = buildTree(0, 199)

CEO.left # CTO 负责0~99
CEO.right # CFO 负责100~199

Query: # of nodes visited: Average and worst are both ~O(logn)

## Applications

LeetCode 307 Range Sum Query – Mutable

## Python3

Problem:

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

Idea:

Fenwick Tree

Solution:

C++

Time complexity:

init O(nlogn)

query: O(logn)

update: O(logn)