Dynamic Range Subarray Sum with Transformations

Data Structure Design

Design a data structure that maintains a dynamic 0-indexed array of integers and supports point insertions, point deletions, range reversals, range cyclic rotations, and maximum contiguous subarray sum range queries.

Your system should process an initial array of integers and a series of dynamic operations. The operations are given as an array of command tuples:

["insert", index, val]: Inserts integer val at position index ($0 \le \text{index} \le \text{current length}$). Elements previously at or after index shift to the right.
["delete", index]: Removes the element at position index ($0 \le \text{index} < \text{current length}$). Elements after index shift to the left.
["reverse", left, right]: Reverses the subsegment of elements from index left to index right inclusive ($0 \le \text{left} \le \text{right} < \text{current length}$).
["rotate", left, right, k]: Cyclically shifts the subsegment of elements from index left to index right inclusive to the right by k non-negative steps ($0 \le \text{left} \le \text{right} < \text{current length}$, $k \ge 0$).
["query", left, right]: Returns the maximum contiguous subarray sum within the range [left, right] inclusive ($0 \le \text{left} \le \text{right} < \text{current length}$). The contiguous subarray must contain at least one element.

Return a list of integer outputs corresponding to each query operation in the order they are executed.

Example 1

Input

[
  "[1, -2, 3, 4, -1, 2]",
  "[[\"query\", 0, 5], [\"insert\", 2, 5], [\"rotate\", 1, 4, 2], [\"reverse\", 0, 3], [\"query\", 1, 5], [\"delete\", 3], [\"query\", 0, 5]]"
]

Output

[8, 13, 13]

Explanation. Initial array: [1, -2, 3, 4, -1, 2]. query(0,5) gives max subarray [3, 4, -1, 2] with sum 8. After insert(2, 5), array is [1, -2, 5, 3, 4, -1, 2]. rotate(1, 4, 2) turns subsegment [-2, 5, 3, 4] into [3, 4, -2, 5], array becomes [1, 3, 4, -2, 5, -1, 2]. reverse(0, 3) turns [1, 3, 4, -2] into [-2, 4, 3, 1], array becomes [-2, 4, 3, 1, 5, -1, 2]. query(1, 5) on [4, 3, 1, 5, -1] yields max sum 13 ([4, 3, 1, 5]). delete(3) removes index 3 (value 1), leaving [-2, 4, 3, 5, -1, 2]. query(0, 5) gives max sum 13.

Example 2

Input

[
  "[-5, -1, -8, -2]",
  "[[\"query\", 0, 3], [\"insert\", 2, -3], [\"reverse\", 0, 4], [\"rotate\", 1, 3, 1], [\"query\", 0, 4], [\"query\", 0, 1]]"
]

Output

[-1, -1, -1]

Explanation. All elements remain negative or zero-like throughout all transformations. Since subarrays must be non-empty, the maximum contiguous subarray sum is the maximum single element -1 in all queries.

Example 3

Input

[
  "[10, 20, 30]",
  "[[\"query\", 0, 2], [\"rotate\", 0, 2, 5], [\"query\", 0, 2]]"
]

Output

[60, 60]

Explanation. Initially query(0, 2) sums all positive elements to 60. Rotating [10, 20, 30] right by 5 steps (equivalent to 2 steps) results in [20, 30, 10]. The total sum across the range remains 60.

Example 4

Input

[
  "[3, -1, 4, -1, 5, -9, 2, 6, -5, 3]",
  "[[\"query\", 0, 4], [\"reverse\", 2, 6], [\"query\", 2, 6], [\"delete\", 0], [\"delete\", 0], [\"query\", 0, 7]]"
]

Output

[10, 8, 14]

Explanation. First query on [3, -1, 4, -1, 5] yields max sum 10. Reversing indices 2..6 transforms the subsegment [4, -1, 5, -9, 2] into [2, -9, 5, -1, 4]. Query on range 2..6 ([2, -9, 5, -1, 4]) gives max subarray [5, -1, 4] with sum 8. Deleting index 0 twice leaves [2, -9, 5, -1, 4, 6, -5, 3]. Query on range 0..7 yields max subarray [5, -1, 4, 6] with sum 14.

Follow-up: Can you implement all update and query operations in O(log N) expected or amortized time complexity using an Implicit Treap or Splay Tree?

Constraints:

1 <= N <= 10^5 (length of initial array) 1 <= Q <= 10^5 (number of operations) -10^9 <= val <= 10^9 0 <= index <= current length (for insert) 0 <= index < current length (for delete) 0 <= left <= right < current length (for reverse, rotate, query) 0 <= k <= 10^9 The array is guaranteed to contain at least 1 element at all times.

Views: 8