Pizzeria Queries

Problem Overview

Learning Goals

After solving this problem, you will be able to:

• Transform absolute value expressions into range minimum queries
• Recognize when to split |i - j| into two separate cases
• Use two segment trees to handle left and right directions independently
• Apply point updates efficiently with transformed coordinates

Problem Statement

Problem: There are n buildings on a street numbered 1 to n. Each building i has a pizzeria with price p[i]. Handle two query types:

1. Update query: Change the price at building k to x

2. Minimum cost query: Find minimum cost at position k, where cost = price[j] +

   k - j

Input:

• Line 1: n and q (buildings and queries)
• Line 2: n integers p[1]…p[n] (initial prices)
• Next q lines: “1 k x” (update) or “2 k” (query)

Output: For each type-2 query, output the minimum cost

Constraints: 1 <= n, q <= 2*10^5; 1 <= p[i], x <= 10^9

Example

Input:
5 4
3 2 4 1 5
2 3
1 4 8
2 3
2 5

Output:
2
3
5

Explanation:

• Query “2 3”: costs = (5, 3, 4, 2, 7), min = 2 from building 4
• Update “1 4 8”: Price at building 4 becomes 8
• Query “2 3”: costs = (5, 3, 4, 9, 7), min = 3 from building 2
• Query “2 5”: costs = (7, 5, 6, 9, 5), min = 5

Intuition: How to Think About This Problem

The Core Challenge

We need to find: min over all j of (p[j] + |k - j|)

The absolute value is problematic for range queries. The key insight is to split the absolute value based on whether j is left or right of k.

Mathematical Transformation

Case 1: j <= k (pizzeria to the left)

cost = p[j] + (k - j) = (p[j] - j) + k

Case 2: j >= k (pizzeria to the right)

cost = p[j] + (j - k) = (p[j] + j) - k

The Key Insight

Transformation Trick: By rearranging terms, we separate k from pizzeria values:

• min(p[j] - j) for j in [1, k] -> add k for left-side minimum
• min(p[j] + j) for j in [k, n] -> subtract k for right-side minimum

This transforms the problem into two range minimum queries!

Solution 1: Brute Force

def brute_force(n, prices, queries):
  """Time: O(q * n), Space: O(n)"""
  p = prices[:]
  results = []
  for query in queries:
    if query[0] == 1:
      p[query[1] - 1] = query[2]
    else:
      k = query[1]
      min_cost = min(p[j] + abs((k-1) - j) for j in range(n))
      results.append(min_cost)
  return results

With q, n up to 210^5, this gives 410^10 operations - too slow.

Solution 2: Optimal - Two Segment Trees

Data Structure Design

Algorithm

1. Build: left_tree[i] = p[i] - i, right_tree[i] = p[i] + i
2. Update k to x: Update both trees with x - k and x + k
3. Query k: Return min(left_tree.query(1,k) + k, right_tree.query(k,n) - k)

Dry Run Example

Initial (1-indexed): prices = [3, 2, 4, 1, 5]
  p[i] - i:  [2, 0, 1, -3, 0]   (left_tree)
  p[i] + i:  [4, 4, 7, 5, 10]   (right_tree)

Query k=3:
  Left [1,3]:  min(2,0,1) = 0  -> 0 + 3 = 3
  Right [3,5]: min(7,5,10) = 5 -> 5 - 3 = 2
  Answer: min(3, 2) = 2

Update k=4, x=8:
  left_tree[4]  = 8 - 4 = 4
  right_tree[4] = 8 + 4 = 12

Query k=3:
  Left [1,3]:  min(2,0,1) = 0  -> 0 + 3 = 3
  Right [3,5]: min(7,12,10) = 7 -> 7 - 3 = 4
  Answer: min(3, 4) = 3

Code (Python)

import sys
from math import inf

def solve():
  data = sys.stdin.buffer.read().split()
  idx = 0
  n, q = int(data[idx]), int(data[idx+1]); idx += 2

  prices = [0] + [int(data[idx+i]) for i in range(n)]; idx += n

  size = 1
  while size < n: size *= 2

  left_tree = [inf] * (2 * size)
  right_tree = [inf] * (2 * size)

  for i in range(1, n + 1):
    left_tree[size + i - 1] = prices[i] - i
    right_tree[size + i - 1] = prices[i] + i

  for i in range(size - 1, 0, -1):
    left_tree[i] = min(left_tree[2*i], left_tree[2*i+1])
    right_tree[i] = min(right_tree[2*i], right_tree[2*i+1])

  def update(tree, pos, val):
    pos = size + pos - 1
    tree[pos] = val
    pos //= 2
    while pos >= 1:
      tree[pos] = min(tree[2*pos], tree[2*pos+1])
      pos //= 2

  def query(tree, l, r):
    res = inf
    l, r = size + l - 1, size + r - 1
    while l <= r:
      if l % 2 == 1: res = min(res, tree[l]); l += 1
      if r % 2 == 0: res = min(res, tree[r]); r -= 1
      l //= 2; r //= 2
    return res

  results = []
  for _ in range(q):
    t = int(data[idx]); idx += 1
    if t == 1:
      k, x = int(data[idx]), int(data[idx+1]); idx += 2
      update(left_tree, k, x - k)
      update(right_tree, k, x + k)
    else:
      k = int(data[idx]); idx += 1
      left_min = query(left_tree, 1, k) + k
      right_min = query(right_tree, k, n) - k
      results.append(min(left_min, right_min))

  print('\n'.join(map(str, results)))

if __name__ == "__main__":
  solve()

Complexity

Common Mistakes

Mistake 1: Only Updating One Tree

# WRONG
update(left_tree, k, x - k)
# Forgot right_tree!

Fix: Always update both trees on price change.

Mistake 2: Wrong Query Boundaries

# WRONG - excludes k
left_min = query(left_tree, 1, k - 1)

Fix: Include k in both queries: [1, k] and [k, n].

Edge Cases

When to Use This Pattern

Use when:

• Cost formula includes |i - j| (absolute distance)
• You can split into “left” and “right” cases
• After splitting, expressions become range min/max queries
• Point updates are needed

Pattern recognition:

• Nearest facility with costs
• Distance-weighted selection
• Minimum travel cost problems

Related Problems

Easier

Similar Difficulty

LeetCode Related

Key Takeaways

1. Core Idea: Transform min(p[j] + |k-j|) by splitting absolute value into left/right cases

2. Math: |k-j| = k-j when j <= k, and j-k when j >= k. This gives (p[j]-j)+k and (p[j]+j)-k

3. Implementation: Two segment trees storing p[i]-i and p[i]+i, query both and take minimum

4. Pattern: This “absolute value splitting” technique appears in many distance optimization problems

Practice Checklist

• Derive the transformation from p[j] + |k-j| to two range queries
• Implement segment tree for range minimum with point updates
• Handle both 0-indexed and 1-indexed correctly
• Explain why we need TWO segment trees
• Solve in under 20 minutes