Examples Pick ONE option
Grey Orange technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Examples
arr = [1, 1, 1, 1, 1, 1, 1]
arr' = [1, 2, 1, 4, 1, 2, 1, 8]
arr = [1, 2, 3, 4, 5, 6, 7, 8]
arr' = [1, 3, 3, 10, 5, 6, 7, 36]
Pick ONE option
Show answer & explanation
The problem describes a pattern of updating and querying elements based on index properties. A Binary Indexed Tree (Fenwick Tree) is the optimal data structure for handling prefix sums and point updates in O(log n) time, which aligns with the requirement to manage sums of specific index subsets efficiently.
Step-by-step Derivation:
Step 1: Analyze the requirement. The goal is to maintain a sum of elements at specific indices (even indices) while allowing for updates and prefix sum queries.
Step 2: Evaluate Option A. A simple prefix sum array allows O(1) query time but requires O(n) time for updates, making it inefficient for dynamic data.
Step 3: Evaluate Option B. A Binary Indexed Tree (BIT) allows both updates and prefix sum queries in O(log n) time. By mapping the even indices to a BIT, we can efficiently maintain the sum of elements at those positions.
Step 4: Compare with other options. Segment trees (Option C) are also viable but typically more complex to implement than BITs for simple prefix sums. Iterating the array (Option D) results in O(n^2) complexity for multiple queries.
Step 5: Conclusion. Given the standard algorithmic patterns for 'prefix sums' and 'updates', the Binary Indexed Tree is the most technically appropriate choice for this specific set of operations.