Standard segment tree compositions assume that a node's summary statistics depend exclusively on its immediate children. However, problems involving prefix constraints or running extrema require contextual awarreness—aggregation of the right subtree depends on specific values emanating from the left. Unilateral recursion resolves this by descending into only the relevant child during merge operations, maintaining logarithmic complexity.

Prefix Maximum Counting

Consider a dynamic array where we must count prefix maximums—elements greater than all predecessors—supporting point updates. Each segment tree node stores cnt (the count of prefix maximums in its interval) and range_max (the interval's maximum value). When merging, the right child's prefix maximums are only valid if they exceed the left child's global maximum.

The merge operation requires counting elements in the right subtree that exceed the left subtree's maximum. We implement a threshold-sensitive query that traverses only the necessary branches:

int count_above(double limit, int l, int r, int idx) {
    if (range_max[idx] <= limit) return 0;
    if (l == r) return 1;
    int mid = (l + r) >> 1;
    if (range_max[left_idx] <= limit) 
        return count_above(limit, mid + 1, r, right_idx);
    return pref_cnt[idx] - pref_cnt[left_idx] + 
           count_above(limit, l, mid, left_idx);
}

void pull_up(int l, int r, int idx) {
    int mid = (l + r) >> 1;
    pref_cnt[idx] = pref_cnt[left_idx] + 
                    count_above(range_max[left_idx], mid + 1, r, right_idx);
    range_max[idx] = max(range_max[left_idx], range_max[right_idx]);
}

When the left child's maximum dominates the incoming threshold, the function bypasses the left subtree entirely—the right subtree receives the original threshold. Otherwise, it recurses into the left subtree while utilizing the cached difference pref_cnt[idx] - pref_cnt[left_idx] to account for the right subtree's contribution under the left child's maximum constraint. Each merge performs O(log n) work, yielding O(log² n) per update.

Distinct Elemants via Last Occurrence

This technique extends to counting distinct values using the previous-occurrence array prev[i]. The number of distinct elements in prefix i equals i - max(prev[1..i]). For range queries, we maintain the sum of these running maximums.

The segment tree stores sum_max (the sum of max-prev values) and range_max (the maximum prev in the interval). The merge logic mirrors the prefix maximum problem, aggregating sums rather than counts:

long long sum_with_floor(int floor_val, int l, int r, int idx) {
    if (range_max[idx] <= floor_val) 
        return (long long)floor_val * (r - l + 1);
    if (l == r) return sum_max[idx];
    int mid = (l + r) >> 1;
    if (range_max[left_idx] <= floor_val) 
        return (long long)floor_val * (mid - l + 1) + 
               sum_with_floor(floor_val, mid + 1, r, right_idx);
    return sum_max[idx] - sum_max[left_idx] + 
           sum_with_floor(floor_val, l, mid, left_idx);
}

void pull_up(int l, int r, int idx) {
    int mid = (l + r) >> 1;
    sum_max[idx] = sum_max[left_idx] + 
                   sum_with_floor(range_max[left_idx], mid + 1, r, right_idx);
    range_max[idx] = max(range_max[left_idx], range_max[right_idx]);
}

For arbitrary range queries, we decompose the interval and propagate the maximum prev value encountered, combining partial results using the same unilateral descent strategy.

Maximum Subarray with Color Constraints

The pattern adapts to weighted distinct-value problems: finding the maximum subarray sum where no value repeats (enforced via the prev array). The optimal subarray ending at position i starts after max(prev[1..i]). We maintain the maximum valid subarray sum for each segment under hypothetical boundary constraints.

The query returns the best achievable sum given a minimum start position constraint:

long long query_best(int min_pos, int l, int r, int idx) {
    if (range_max[idx] <= min_pos) return prefix_sum[r] - prefix_sum[min_pos];
    if (l == r) return best_val[idx];
    int mid = (l + r) >> 1;
    if (range_max[left_idx] <= min_pos) 
        return max(query_best(min_pos, l, mid, left_idx),
                   query_best(min_pos, mid + 1, r, right_idx));
    return max(query_best(min_pos, l, mid, left_idx), 
               right_cached[idx]);
}

void pull_up(int l, int r, int idx) {
    int mid = (l + r) >> 1;
    range_max[idx] = max(range_max[left_idx], range_max[right_idx]);
    right_cached[idx] = query_best(range_max[left_idx], mid + 1, r, right_idx);
    best_val[idx] = max(best_val[left_idx], right_cached[idx]);
}

Here right_cached stores the precomptued result for the right child under the left child's maximum constraint, enabling O(1) composition during merges while preserving O(log n) complexity for arbitrary threshold queries. This unilateral descent—probing only the subtree containing threshold violations—ensures efficient handling of merge dependencies that would otherwise require linear reconciliation.