Stage 4: Advanced Techniques·Segment Tree & BIT

Hard#24078 min readSegment TreeDynamic ProgrammingLeetCode

Longest Increasing Subsequence II

Segment tree on value range

Segment tree optimization on DP transitions. The ‘DP + data structure’ pattern.

Published Apr 16, 2026

Problem

Given an integer array nums and an integer k, find the length of the longest strictly increasing subsequence such that the difference between adjacent elements is at most k.

Input

nums = [4, 2, 1, 4, 3, 4, 5, 8, 15], k = 3

Output

Explanation

One valid subsequence: [1, 3, 4, 5, 8]. Each consecutive pair differs by at most 3.

Input

nums = [7, 4, 5, 1, 8, 12, 4, 7], k = 5

Output

Explanation

One valid subsequence: [4, 5, 8, 12].

Input

nums = [1, 5], k = 1

Output

Explanation

5 - 1 = 4 > k. No pair qualifies. Longest is a single element.

Intuition

Classic LIS is O(n²) DP or O(n log n) patience sort. The gap-k constraint makes patience sort awkward, but opens a different optimization path.

Let dp[v] = the longest valid subsequence ending with value v. For each nums[i]:

dp[nums[i]] = 1 + max(dp[v] for v in [nums[i] - k, nums[i] - 1])

The inner max is a range-max query over a value-indexed array. A segment tree answers it in O(log V) per element, and the point update dp[nums[i]] = new_value is also O(log V). Total: O(n log V) where V is the value range (up to 10^5).

Approach

DP Brute Force

TimeO(n²)

SpaceO(n)

For each i, scan all j < i with nums[j] < nums[i] and nums[i] - nums[j] <= k.

impl Solution {
    pub fn length_of_lis(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let mut dp = vec![1; n];
        let mut best = 1;
        for i in 1..n {
            for j in 0..i {
                if nums[j] < nums[i] && nums[i] - nums[j] <= k {
                    dp[i]= dp[i].max(dp[j] + 1);
                }
            }
            best= best.max(dp[i]);
        }
        best
    }
}

Rust · runnable

function lengthOfLIS(nums: number[], k: number): number {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  let best = 1;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i] && nums[i] - nums[j] <= k) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    best = Math.max(best, dp[i]);
  }
  return best;
}

TypeScript · runnable

Segment Tree on Value Range

TimeO(n log V)

SpaceO(V)

Recommended

Build a max-segment-tree over the value range [0, max_val]. For each element, query max(tree[nums[i] - k .. nums[i] - 1]), set tree[nums[i]] = query_result + 1, and track the global maximum.

impl Solution {
    pub fn length_of_lis(nums: Vec<i32>, k: i32) -> i32 {
        let max_val = *nums.iter().max().unwrap() as usize;
        let size = max_val + 1;
        let mut tree = vec![0i32; 4 * size.max(1)];

        fn query(t: &[i32], node: usize, lo: usize, hi: usize, ql: usize, qr: usize) -> i32 {
            if qr < lo || hi < ql || ql > qr { return 0; }
            if ql <= lo && hi <= qr { return t[node]; }
            let mid= (lo + hi) / 2;
            query(t, 2 * node, lo, mid, ql, qr)
                .max(query(t, 2 * node + 1, mid + 1, hi, ql, qr))
        }

        fn update(t: &mut [i32], node: usize, lo: usize, hi: usize, pos: usize, val: i32) {
            if lo= hi { t[node]= t[node].max(val); return; }
            let mid= (lo + hi) / 2;
            if pos <= mid { update(t, 2 * node, lo, mid, pos, val); }
            else { update(t, 2 * node + 1, mid + 1, hi, pos, val); }
            t[node]= t[2 * node].max(t[2 * node + 1]);
        }

        let mut best= 1;
        for &x in &nums {
            let v= x as usize;
            let lo_q= if v as i32 - k >= 0 { (v as i32 - k) as usize } else { 0 };
            let hi_q = if v > 0 { v - 1 } else { 0 };
            let prev = if lo_q <= hi_q {
                query(&tree, 1, 0, max_val, lo_q, hi_q)
            } else {
                0
            };
            let cur= prev + 1;
            update(&mut tree, 1, 0, max_val, v, cur);
            if cur > best { best = cur; }
        }

        best
    }
}

Rust · runnable

function lengthOfLIS(nums: number[], k: number): number {
  const maxVal = Math.max(...nums);
  const size = maxVal + 1;
  const tree = new Array(4 * Math.max(size, 1)).fill(0);

  const query = (node: number, lo: number, hi: number, ql: number, qr: number): number => {
    if (qr < lo || hi < ql || ql > qr) return 0;
    if (ql <= lo && hi <= qr) return tree[node];
    const mid = (lo + hi) >> 1;
    return Math.max(
      query(2 * node, lo, mid, ql, qr),
      query(2 * node + 1, mid + 1, hi, ql, qr),
    );
  };

  const update = (node: number, lo: number, hi: number, pos: number, val: number): void => {
    if (lo === hi) { tree[node] = Math.max(tree[node], val); return; }
    const mid = (lo + hi) >> 1;
    if (pos <= mid) update(2 * node, lo, mid, pos, val);
    else update(2 * node + 1, mid + 1, hi, pos, val);
    tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);
  };

  let best = 1;
  for (const x of nums) {
    const lo = Math.max(0, x - k);
    const hi = x - 1;
    const prev = lo <= hi ? query(1, 0, maxVal, lo, hi) : 0;
    const cur = prev + 1;
    update(1, 0, maxVal, x, cur);
    if (cur > best) best = cur;
  }

  return best;
}

TypeScript · runnable

Trace

nums = [4, 2, 1, 4, 3, 4, 5, 8, 15], k = 3:

i	val	query range	prev max	dp[val]	global best
0	4	[1..3]	0	1	1
1	2	[0..1]	0	1	1
2	1	[0..0]	0	1	1
3	4	[1..3]	1 (val 2 or 1)	2	2
4	3	[0..2]	1 (val 1 or 2)	2	2
5	4	[1..3]	2 (val 3)	3	3
6	5	[2..4]	3 (val 4)	4	4
7	8	[5..7]	4 (val 5)	5	5
8	15	[12..14]	0	1	5

Edge cases

k = 0 — no increase allowed. Every subsequence is a single element. Answer is 1.
All same values — strictly increasing means no pair qualifies. Answer is 1.
Strictly increasing within k — full array is valid.
Large value range — segment tree size is O(max_val). If values are sparse but large, coordinate compression reduces to O(n) nodes.

Takeaway

LIS with a value-gap constraint maps naturally to a segment tree on the value domain. The DP recurrence becomes a range-max query + point update, both O(log V). This technique generalizes: any DP where the transition scans a sliding window of values (not indices) can be accelerated the same way.

Medium#307

Range Sum Query - Mutable

Classic segment tree. Build, update, query. Implement from scratch in Rust.

Hard#315

Count of Smaller Numbers After Self

BIT or merge sort. Process right to left, count elements smaller than current.

Medium#300

Longest Increasing Subsequence

O(n²) DP first, then learn the O(n log n) patience sorting approach.