Palindrome Queries

Problem Overview

Learning Goals

After solving this problem, you will be able to:

• Combine string hashing with segment trees for dynamic updates
• Use polynomial hashing to compare substrings in O(1) time
• Build segment trees that maintain hash values with point updates
• Handle forward and reverse hash computations for palindrome checking

Problem Statement

Problem: You have a string of n characters and m queries. There are two types of queries:

1. Update (type 1): Change character at position k to character x
2. Query (type 2): Check if substring from position a to b is a palindrome

Input:

• Line 1: Two integers n and m (string length and number of queries)
• Line 2: A string of n lowercase characters
• Next m lines: Query type followed by parameters (1 k x or 2 a b)

Output:

• For each type 2 query, print “YES” if the substring is a palindrome, “NO” otherwise

Constraints:

• 1 <= n, m <= 2 * 10^5
• 1 <= k <= n, 1 <= a <= b <= n
• String contains only lowercase English letters

Example

Input:
7 5
aybabtu
2 3 5
1 3 b
2 3 5
1 5 a
2 3 5

Output:
NO
YES
YES

Explanation: (1-indexed)

• Initial: “aybabtu”, s[3..5]=”bab” - checking reveals NO
• Update s[3]=’b’: “ayabbtu”, s[3..5]=”abb” - wait, let’s trace carefully
• The key insight: algorithm compares forward and reverse hashes

Intuition: How to Think About This Problem

Pattern Recognition

Key Question: How do we efficiently check if a substring is a palindrome when the string can change?

A palindrome reads the same forwards and backwards. We need to compare s[a..b] with its reverse. With point updates, precomputation alone won’t work - we need a data structure that supports both updates and range queries.

Breaking Down the Problem

1. What are we looking for? Whether s[a..b] equals its reverse s[b..a] (reading backwards)
2. What information do we have? A mutable string and range queries
3. What’s the relationship? If forward_hash(a,b) == reverse_hash(a,b), it’s a palindrome

The Key Insight

Core Idea: Use two segment trees - one for forward hashes, one for reverse hashes. A substring is a palindrome if and only if its forward hash equals its reverse hash.

Why Segment Tree? It supports:

• Point updates in O(log n)
• Range queries in O(log n)
• We can store polynomial hash contributions at each node

Solution: Hashing + Segment Tree

Key Insight

The Trick: Maintain polynomial hashes in segment trees. Each leaf stores character’s hash contribution. Internal nodes combine children’s hashes using polynomial multiplication.

Hash Function Design

For a string s, the polynomial hash is:

H(s) = s[0] * P^(n-1) + s[1] * P^(n-2) + ... + s[n-1] * P^0

Where P is a prime base (e.g., 31) and all operations are mod M (e.g., 10^9 + 7).

Segment Tree Structure

How Segment Tree Nodes Combine

When merging left child (hash_L, len_L) and right child (hash_R, len_R):

combined_hash = hash_L * P^(len_R) + hash_R

This correctly computes the polynomial hash of the concatenated string.

Dry Run Example

Let’s trace through with string “abcba” and query (1, 5):

String: a  b  c  b  a       Forward hash: a*P^4 + b*P^3 + c*P^2 + b*P^1 + a*P^0
Index:  1  2  3  4  5       Reverse hash: a*P^4 + b*P^3 + c*P^2 + b*P^1 + a*P^0
                            Equal => Palindrome!

Non-palindrome "abcde":
Forward:  a*P^4 + b*P^3 + c*P^2 + d*P^1 + e*P^0
Reverse:  e*P^4 + d*P^3 + c*P^2 + b*P^1 + a*P^0  => Different, not palindrome

Visual Diagram

Segment Tree for "abcba":     Each leaf: hash = (char - 'a' + 1)
        [abcba]               Internal: hash = left * P^(right_len) + right
       /       \
    [abc]      [ba]
    /   \      /  \
  [ab]  [c]  [b]  [a]

Algorithm

1. Precompute powers of P up to n
2. Build forward segment tree (left-to-right hash)
3. Build reverse segment tree (right-to-left hash)
4. For update: modify both trees at the position
5. For query: compare forward_hash(a,b) with reverse_hash(a,b)

Code (Python)

import sys
def solve():
  input = sys.stdin.readline
  MOD, BASE = 10**9 + 7, 31
  n, m = map(int, input().split())
  s = list(input().strip())

  pw = [1] * (n + 1)
  for i in range(1, n + 1): pw[i] = pw[i-1] * BASE % MOD
  fwd, rev = [0] * (4 * n), [0] * (4 * n)

  def char_val(c): return ord(c) - ord('a') + 1

  def build(node, lo, hi):
    if lo == hi:
      fwd[node] = rev[node] = char_val(s[lo])
      return
    mid = (lo + hi) // 2
    build(2*node, lo, mid)
    build(2*node+1, mid+1, hi)
    right_len, left_len = hi - mid, mid - lo + 1
    fwd[node] = (fwd[2*node] * pw[right_len] + fwd[2*node+1]) % MOD
    rev[node] = (rev[2*node+1] * pw[left_len] + rev[2*node]) % MOD

  def update(node, lo, hi, pos, val):
    if lo == hi:
      fwd[node] = rev[node] = val
      return
    mid = (lo + hi) // 2
    if pos <= mid: update(2*node, lo, mid, pos, val)
    else: update(2*node+1, mid+1, hi, pos, val)
    right_len, left_len = hi - mid, mid - lo + 1
    fwd[node] = (fwd[2*node] * pw[right_len] + fwd[2*node+1]) % MOD
    rev[node] = (rev[2*node+1] * pw[left_len] + rev[2*node]) % MOD

  def query_fwd(node, lo, hi, l, r):
    if r < lo or hi < l: return (0, 0)
    if l <= lo and hi <= r: return (fwd[node], hi - lo + 1)
    mid = (lo + hi) // 2
    L, R = query_fwd(2*node, lo, mid, l, r), query_fwd(2*node+1, mid+1, hi, l, r)
    if L[1] == 0: return R
    if R[1] == 0: return L
    return ((L[0] * pw[R[1]] + R[0]) % MOD, L[1] + R[1])

  def query_rev(node, lo, hi, l, r):
    if r < lo or hi < l: return (0, 0)
    if l <= lo and hi <= r: return (rev[node], hi - lo + 1)
    mid = (lo + hi) // 2
    L, R = query_rev(2*node, lo, mid, l, r), query_rev(2*node+1, mid+1, hi, l, r)
    if L[1] == 0: return R
    if R[1] == 0: return L
    return ((R[0] * pw[L[1]] + L[0]) % MOD, L[1] + R[1])

  build(1, 0, n-1)
  results = []
  for _ in range(m):
    q = input().split()
    if q[0] == '1':
      k, x = int(q[1]) - 1, q[2]
      s[k] = x
      update(1, 0, n-1, k, char_val(x))
    else:
      a, b = int(q[1]) - 1, int(q[2]) - 1
      results.append("YES" if query_fwd(1,0,n-1,a,b)[0] == query_rev(1,0,n-1,a,b)[0] else "NO")
  print('\n'.join(results))

if __name__ == "__main__": solve()

Complexity

Common Mistakes

Mistake 1: Wrong Hash Combination Order

Problem: Reverse tree must combine children in opposite order. Fix: For reverse: rev[node] = (rev[2*node+1] * pw[left_len] + rev[2*node]) % MOD

Mistake 2: Forgetting to Handle Query Segment Merging

Problem: Polynomial hash requires proper power multiplication. Fix: return {(lhash * pw[rlen] + rhash) % MOD, llen + rlen}

Mistake 3: Off-by-One in Indexing

Problem: CSES uses 1-indexed input, but segment tree often uses 0-indexed. Fix: Always convert: k = input_k - 1

Mistake 4: Integer Overflow

Problem: Values can overflow even with long long. Fix: Apply MOD after each multiplication.

Edge Cases

When to Use This Pattern

Use This Approach When:

• String has point updates AND range palindrome queries
• Need O(log n) per operation
• Single hash is acceptable (low collision probability)

Don’t Use When:

• No updates (use simple prefix hashes with O(1) queries)
• Need guaranteed correctness (use double hashing or verification)
• Memory is very limited (segment tree uses 4n space)

Pattern Recognition Checklist:

• Dynamic string with modifications? -> Segment Tree
• Comparing substrings? -> Hashing
• Palindrome = forward equals reverse? -> Two hash structures
• Need fast range queries + updates? -> Segment Tree with lazy propagation (if range updates)

Related Problems

Easier (Do These First)

Similar Difficulty

Harder (Do These After)

Key Takeaways

1. Core Idea: Two segment trees (forward/reverse hash) enable O(log n) palindrome checks with updates
2. Time Optimization: From O(n) per query to O(log n) using segment trees
3. Space Trade-off: O(n) extra space for 4n segment tree nodes
4. Pattern: “Dynamic string + range queries” often means Segment Tree + Hashing

Practice Checklist

Before moving on, make sure you can:

• Explain why we need two separate segment trees
• Derive the hash combination formula for both forward and reverse
• Implement the solution without looking at the code
• Handle the indexing conversion correctly
• Identify hash collision risks and mitigation strategies

Additional Resources

• CP-Algorithms: String Hashing
• CP-Algorithms: Segment Tree
• CSES Palindrome Queries - Dynamic palindrome checking