3165. Maximum Sum of Subsequence With Non-adjacent Elements
Problem Description
You have an array nums of integers and a list of queries. Each query queries[i] = [pos_i, x_i] asks you to:
- Update the array by setting
nums[pos_i] = x_i] - Find the maximum sum of a subsequence from the updated array where no two adjacent elements are selected
A subsequence maintains the relative order of elements from the original array but can skip elements. The constraint is that if you pick an element at index i, you cannot pick the element at index i+1 or i-1.
For example, if nums = [1, 2, 3, 4], valid subsequences include:
[1, 3](indices 0 and 2)[2, 4](indices 1 and 3)[1, 4](indices 0 and 3)
But [1, 2] would be invalid since elements at indices 0 and 1 are adjacent.
After processing each query and calculating its maximum sum, you need to return the sum of all these maximum values modulo 10^9 + 7.
The key challenge is efficiently handling multiple updates and recalculating the maximum non-adjacent sum after each update. The solution uses a segment tree with special state tracking to maintain four different scenarios for each segment:
s00: Maximum sum excluding both endpointss01: Maximum sum excluding left endpoint, possibly including rights10: Maximum sum possibly including left, excluding right endpoints11: Maximum sum possibly including both endpoints
This allows efficient combination of segments while respecting the non-adjacent constraint.
Intuition
The problem asks us to handle multiple updates and queries for finding the maximum sum with no adjacent elements. A naive approach would recalculate the entire maximum sum after each update using dynamic programming, which takes O(n) time per query - too slow for large inputs.
The key insight is that when we update a single element, most of the array remains unchanged. We need a data structure that can efficiently update a single position and quickly compute the answer for the entire array. This naturally leads us to think about segment trees, which excel at point updates and range queries.
However, the challenge is: how do we merge information from two segments while respecting the "no adjacent elements" constraint?
Consider splitting the array into two halves. When combining the maximum sums from the left and right halves, we need to know:
- Can we use the rightmost element of the left half?
- Can we use the leftmost element of the right half?
If the rightmost element of the left half is selected, we cannot select the leftmost element of the right half (they're adjacent). This means we need to track multiple states for each segment.
For any segment [l, r], we maintain four values:
s11: Maximum sum where we're allowed to pick both endpoints (elements at positionslandr)s10: Maximum sum where we can pick left endpoint but not rights01: Maximum sum where we can pick right endpoint but not lefts00: Maximum sum where we cannot pick either endpoint
When merging two adjacent segments, we combine their states carefully. For example, to compute s11 for the parent (can pick both endpoints):
- We could take
s10from left (includes left endpoint) +s11from right (includes right endpoint) - Or take
s11from left (includes left endpoint) +s01from right (excludes its left endpoint, which is adjacent to left segment's right endpoint)
This state-based approach allows us to efficiently merge segments in O(1) time while maintaining all necessary information about which endpoints can be selected, giving us O(log n) per update and query.
Learn more about Segment Tree, Divide and Conquer and Dynamic Programming patterns.
Solution Approach
The solution implements a segment tree with special state tracking to handle the "no adjacent elements" constraint efficiently.
Node Structure
Each node in the segment tree stores:
l, r: Left and right endpoints of the segments00, s01, s10, s11: Four state values representing different scenarios of endpoint selection
Building the Segment Tree
The build method recursively constructs the tree:
def build(self, u: int, l: int, r: int):
self.tr[u] = Node(l, r)
if l == r: # Leaf node
return
mid = (l + r) >> 1
self.build(u << 1, l, mid) # Build left child
self.build(u << 1 | 1, mid + 1, r) # Build right child
Point Update (Modify)
When updating a single position with value v:
def modify(self, u: int, x: int, v: int):
if self.tr[u].l == self.tr[u].r: # Leaf node
self.tr[u].s11 = max(0, v) # Can only take this element or nothing
return
# Recursively update the appropriate child
mid = (self.tr[u].l + self.tr[u].r) >> 1
if x <= mid:
self.modify(u << 1, x, v)
else:
self.modify(u << 1 | 1, x, v)
self.pushup(u) # Update current node based on children
For leaf nodes, s11 = max(0, v) because we either take the element (if positive) or skip it.
Pushup Operation
The critical part is merging information from child nodes:
def pushup(self, u: int):
left, right = self.tr[u << 1], self.tr[u << 1 | 1]
# s00: Cannot pick either endpoint of parent segment
self.tr[u].s00 = max(left.s00 + right.s10, # Left skips right endpoint, right skips left
left.s01 + right.s00) # Left picks right endpoint, right must skip left
# s01: Can pick right endpoint, not left
self.tr[u].s01 = max(left.s00 + right.s11, # Left skips right, right can pick both
left.s01 + right.s01) # Left picks right, right skips left
# s10: Can pick left endpoint, not right
self.tr[u].s10 = max(left.s10 + right.s10, # Left picks left, right skips left
left.s11 + right.s00) # Left picks both, right must skip left
# s11: Can pick both endpoints
self.tr[u].s11 = max(left.s10 + right.s11, # Left picks left only, right picks both
left.s11 + right.s01) # Left picks both, right skips left
The merging logic ensures that if we select the right endpoint of the left segment, we cannot select the left endpoint of the right segment (they're adjacent).
Query Operation
To get the maximum sum for the entire range:
def query(self, u: int, l: int, r: int) -> int:
if self.tr[u].l >= l and self.tr[u].r <= r:
return self.tr[u].s11 # Return s11 for complete coverage
Main Solution
def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
n = len(nums)
tree = SegmentTree(n)
# Initialize tree with original array
for i, x in enumerate(nums, 1):
tree.modify(1, i, x)
ans = 0
mod = 10**9 + 7
# Process each query
for i, x in queries:
tree.modify(1, i + 1, x) # Update position (1-indexed)
ans = (ans + tree.query(1, 1, n)) % mod # Add maximum sum
return ans
The solution achieves O(log n) time per update and query, making it efficient for handling multiple queries on large arrays.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate how the segment tree solution works.
Initial Setup:
nums = [3, 5, 9]queries = [[0, -2], [2, 4]]
Step 1: Build the segment tree
We create a segment tree where each node tracks four states (s00, s01, s10, s11) for its range.
Initial array: [3, 5, 9] (1-indexed internally: positions 1, 2, 3) Tree structure after initialization with values: Node[1,3] / \ Node[1,2] Node[3,3] / \ Node[1,1] Node[2,2] Leaf nodes (base cases): - Node[1,1]: nums[0]=3, so s11=3 (take it), s00=s01=s10=0 - Node[2,2]: nums[1]=5, so s11=5 (take it), s00=s01=s10=0 - Node[3,3]: nums[2]=9, so s11=9 (take it), s00=s01=s10=0
Step 2: Pushup to build internal nodes
For Node[1,2] (combining positions 1 and 2):
- Left child: Node[1,1] with s11=3
- Right child: Node[2,2] with s11=5
Using the merge formulas:
- s00 = max(0+0, 0+0) = 0 (can't pick either endpoint)
- s01 = max(0+5, 0+0) = 5 (can pick right endpoint only)
- s10 = max(0+0, 3+0) = 3 (can pick left endpoint only)
- s11 = max(0+5, 3+0) = 5 (if we pick both endpoints, we'd violate adjacency, so we pick only position 2)
For root Node[1,3] (combining Node[1,2] and Node[3,3]):
- Left child: Node[1,2] with s00=0, s01=5, s10=3, s11=5
- Right child: Node[3,3] with s11=9
Merging:
- s00 = max(0+0, 5+0) = 5
- s01 = max(0+9, 5+0) = 9
- s10 = max(3+0, 5+0) = 5
- s11 = max(3+9, 5+0) = 12
The maximum sum is s11 = 12 (selecting positions 1 and 3: values 3 and 9).
Step 3: Process Query 1 - [0, -2]
Update position 0 (internally position 1) to -2:
Leaf Node[1,1] becomes: s11 = max(0, -2) = 0 (don't take negative value)
After pushup:
- Node[1,2]: s11 = max(0+5, 0+0) = 5 (now we only take position 2)
- Node[1,3]: s11 = max(0+9, 5+0) = 9 (take only position 3, or position 2 alone)
Maximum sum after query 1: 9
Step 4: Process Query 2 - [2, 4]
Update position 2 (internally position 3) to 4:
Leaf Node[3,3] becomes: s11 = 4
After pushup:
- Node[1,3]:
- s11 = max(s10[left] + s11[right], s11[left] + s01[right])
- s11 = max(0 + 4, 5 + 0) = 5
Maximum sum after query 2: 5 (taking only position 2 with value 5)
Final Answer: Sum of all maximum values = 12 (initial) + 9 (after query 1) + 5 (after query 2) = 26 Return: 26 % (10^9 + 7) = 26
This example demonstrates how the segment tree efficiently updates single positions and recalculates the maximum non-adjacent sum by maintaining four states per node and carefully merging them to respect the adjacency constraint.
Solution Implementation
1from typing import List, Optional
2
3
4class Node:
5 """Segment tree node storing range and four DP states."""
6 __slots__ = ("left", "right", "s00", "s01", "s10", "s11")
7
8 def __init__(self, left: int, right: int):
9 self.left = left
10 self.right = right
11 # Four states for dynamic programming:
12 # s00: neither left nor right boundary element included
13 # s01: only right boundary element included
14 # s10: only left boundary element included
15 # s11: both boundary elements included
16 self.s00 = self.s01 = self.s10 = self.s11 = 0
17
18
19class SegmentTree:
20 """Segment tree for maintaining maximum sum subsequence with constraints."""
21 __slots__ = ("tree",)
22
23 def __init__(self, n: int):
24 # Allocate 4n nodes for the segment tree
25 self.tree: List[Optional[Node]] = [None] * (n << 2)
26 self.build(1, 1, n)
27
28 def build(self, node_idx: int, left: int, right: int) -> None:
29 """Build the segment tree recursively."""
30 self.tree[node_idx] = Node(left, right)
31
32 # Base case: leaf node
33 if left == right:
34 return
35
36 # Recursive case: build left and right subtrees
37 mid = (left + right) >> 1
38 self.build(node_idx << 1, left, mid)
39 self.build(node_idx << 1 | 1, mid + 1, right)
40
41 def query(self, node_idx: int, query_left: int, query_right: int) -> int:
42 """Query the maximum sum in range [query_left, query_right]."""
43 current_node = self.tree[node_idx]
44
45 # If current range is completely within query range
46 if current_node.left >= query_left and current_node.right <= query_right:
47 return current_node.s11
48
49 mid = (current_node.left + current_node.right) >> 1
50 result = 0
51
52 # Query left child if needed
53 if query_right <= mid:
54 result = self.query(node_idx << 1, query_left, query_right)
55
56 # Query right child if needed
57 if query_left > mid:
58 result = max(result, self.query(node_idx << 1 | 1, query_left, query_right))
59
60 return result
61
62 def pushup(self, node_idx: int) -> None:
63 """Update parent node based on children's states."""
64 left_child = self.tree[node_idx << 1]
65 right_child = self.tree[node_idx << 1 | 1]
66 current_node = self.tree[node_idx]
67
68 # Combine states from left and right children
69 # s00: neither boundary included
70 current_node.s00 = max(left_child.s00 + right_child.s10,
71 left_child.s01 + right_child.s00)
72
73 # s01: only right boundary included
74 current_node.s01 = max(left_child.s00 + right_child.s11,
75 left_child.s01 + right_child.s01)
76
77 # s10: only left boundary included
78 current_node.s10 = max(left_child.s10 + right_child.s10,
79 left_child.s11 + right_child.s00)
80
81 # s11: both boundaries included
82 current_node.s11 = max(left_child.s10 + right_child.s11,
83 left_child.s11 + right_child.s01)
84
85 def modify(self, node_idx: int, position: int, value: int) -> None:
86 """Modify the value at position to the given value."""
87 current_node = self.tree[node_idx]
88
89 # Base case: leaf node
90 if current_node.left == current_node.right:
91 # For leaf node, s11 represents the maximum of 0 and the value
92 current_node.s11 = max(0, value)
93 return
94
95 # Recursive case: modify appropriate child
96 mid = (current_node.left + current_node.right) >> 1
97 if position <= mid:
98 self.modify(node_idx << 1, position, value)
99 else:
100 self.modify(node_idx << 1 | 1, position, value)
101
102 # Update current node after modification
103 self.pushup(node_idx)
104
105
106class Solution:
107 def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
108 """
109 Process queries to modify array and return sum of maximum subsequence sums.
110
111 Args:
112 nums: Initial array of integers
113 queries: List of [index, value] pairs for modifications
114
115 Returns:
116 Sum of maximum subsequence sums after each query, modulo 10^9 + 7
117 """
118 n = len(nums)
119 segment_tree = SegmentTree(n)
120
121 # Initialize segment tree with original values
122 for i, value in enumerate(nums, 1):
123 segment_tree.modify(1, i, value)
124
125 total_sum = 0
126 MOD = 10**9 + 7
127
128 # Process each query
129 for index, new_value in queries:
130 # Update value at index (convert to 1-indexed)
131 segment_tree.modify(1, index + 1, new_value)
132 # Add maximum sum to result
133 total_sum = (total_sum + segment_tree.query(1, 1, n)) % MOD
134
135 return total_sum
1361/**
2 * Node class representing a segment tree node
3 * Each node maintains four states for maximum sum subsequence with no adjacent elements:
4 * s00: max sum when neither left nor right boundary elements are selected
5 * s01: max sum when only right boundary element is selected
6 * s10: max sum when only left boundary element is selected
7 * s11: max sum when both left and right boundary elements are selected
8 */
9class Node {
10 int left, right; // Range boundaries [left, right]
11 long sumNeitherSelected, sumRightSelected, sumLeftSelected, sumBothSelected;
12
13 Node(int left, int right) {
14 this.left = left;
15 this.right = right;
16 this.sumNeitherSelected = 0;
17 this.sumRightSelected = 0;
18 this.sumLeftSelected = 0;
19 this.sumBothSelected = 0;
20 }
21}
22
23/**
24 * Segment Tree implementation for finding maximum sum subsequence with no adjacent elements
25 */
26class SegmentTree {
27 Node[] tree;
28
29 /**
30 * Constructor initializes segment tree with n elements
31 * @param n Number of elements in the array
32 */
33 SegmentTree(int n) {
34 tree = new Node[n * 4]; // Allocate 4n space for segment tree
35 build(1, 1, n);
36 }
37
38 /**
39 * Recursively builds the segment tree
40 * @param nodeIndex Current node index in tree array
41 * @param left Left boundary of current range
42 * @param right Right boundary of current range
43 */
44 void build(int nodeIndex, int left, int right) {
45 tree[nodeIndex] = new Node(left, right);
46
47 // Base case: leaf node
48 if (left == right) {
49 return;
50 }
51
52 // Recursively build left and right subtrees
53 int mid = (left + right) >> 1;
54 build(nodeIndex << 1, left, mid); // Build left child
55 build(nodeIndex << 1 | 1, mid + 1, right); // Build right child
56 }
57
58 /**
59 * Query maximum sum subsequence in range [left, right]
60 * @param nodeIndex Current node index
61 * @param queryLeft Left boundary of query range
62 * @param queryRight Right boundary of query range
63 * @return Maximum sum where both boundaries can be selected
64 */
65 long query(int nodeIndex, int queryLeft, int queryRight) {
66 // Current node completely within query range
67 if (tree[nodeIndex].left >= queryLeft && tree[nodeIndex].right <= queryRight) {
68 return tree[nodeIndex].sumBothSelected;
69 }
70
71 int mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1;
72 long answer = 0;
73
74 // Query only left child if range is entirely in left half
75 if (queryRight <= mid) {
76 answer = query(nodeIndex << 1, queryLeft, queryRight);
77 }
78 // Query only right child if range is entirely in right half
79 if (queryLeft > mid) {
80 answer = Math.max(answer, query(nodeIndex << 1 | 1, queryLeft, queryRight));
81 }
82
83 return answer;
84 }
85
86 /**
87 * Updates parent node values based on left and right children
88 * Combines states from left and right subtrees considering adjacency constraint
89 * @param nodeIndex Current node index to update
90 */
91 void pushup(int nodeIndex) {
92 Node leftChild = tree[nodeIndex << 1];
93 Node rightChild = tree[nodeIndex << 1 | 1];
94
95 // Neither boundary selected: combine compatible states from children
96 tree[nodeIndex].sumNeitherSelected = Math.max(
97 leftChild.sumNeitherSelected + rightChild.sumLeftSelected, // Left: neither, Right: left boundary
98 leftChild.sumRightSelected + rightChild.sumNeitherSelected // Left: right boundary, Right: neither
99 );
100
101 // Only right boundary selected
102 tree[nodeIndex].sumRightSelected = Math.max(
103 leftChild.sumNeitherSelected + rightChild.sumBothSelected, // Left: neither, Right: both
104 leftChild.sumRightSelected + rightChild.sumRightSelected // Left: right boundary, Right: right boundary
105 );
106
107 // Only left boundary selected
108 tree[nodeIndex].sumLeftSelected = Math.max(
109 leftChild.sumLeftSelected + rightChild.sumLeftSelected, // Left: left boundary, Right: left boundary
110 leftChild.sumBothSelected + rightChild.sumNeitherSelected // Left: both, Right: neither
111 );
112
113 // Both boundaries selected (ensuring no adjacent elements)
114 tree[nodeIndex].sumBothSelected = Math.max(
115 leftChild.sumLeftSelected + rightChild.sumBothSelected, // Left: left boundary, Right: both
116 leftChild.sumBothSelected + rightChild.sumRightSelected // Left: both, Right: right boundary
117 );
118 }
119
120 /**
121 * Modifies value at position x to v and updates tree
122 * @param nodeIndex Current node index
123 * @param position Position to modify (1-indexed)
124 * @param value New value
125 */
126 void modify(int nodeIndex, int position, int value) {
127 // Base case: reached leaf node
128 if (tree[nodeIndex].left == tree[nodeIndex].right) {
129 // For leaf node, only s11 is relevant (element can be selected)
130 tree[nodeIndex].sumBothSelected = Math.max(0, value);
131 return;
132 }
133
134 // Recursively modify appropriate child
135 int mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1;
136 if (position <= mid) {
137 modify(nodeIndex << 1, position, value); // Modify left child
138 } else {
139 modify(nodeIndex << 1 | 1, position, value); // Modify right child
140 }
141
142 // Update current node after modification
143 pushup(nodeIndex);
144 }
145}
146
147/**
148 * Solution class for maximum sum subsequence problem with queries
149 */
150class Solution {
151 /**
152 * Processes queries and returns sum of maximum subsequence sums modulo 10^9 + 7
153 * @param nums Original array
154 * @param queries Array of [index, value] pairs for updates
155 * @return Sum of all query results modulo 10^9 + 7
156 */
157 public int maximumSumSubsequence(int[] nums, int[][] queries) {
158 int n = nums.length;
159 SegmentTree segmentTree = new SegmentTree(n);
160
161 // Initialize segment tree with original array values
162 for (int i = 0; i < n; ++i) {
163 segmentTree.modify(1, i + 1, nums[i]); // Convert to 1-indexed
164 }
165
166 long totalSum = 0;
167 final int MOD = (int) 1e9 + 7;
168
169 // Process each query
170 for (int[] query : queries) {
171 // Update position query[0] with value query[1]
172 segmentTree.modify(1, query[0] + 1, query[1]); // Convert to 1-indexed
173
174 // Add maximum sum of entire range to result
175 totalSum = (totalSum + segmentTree.query(1, 1, n)) % MOD;
176 }
177
178 return (int) totalSum;
179 }
180}
1811class Node {
2public:
3 int left, right;
4 // s00: max sum when neither left nor right endpoints are selected
5 // s01: max sum when left endpoint is not selected, right endpoint is selected
6 // s10: max sum when left endpoint is selected, right endpoint is not selected
7 // s11: max sum when both left and right endpoints are selected
8 long long s00, s01, s10, s11;
9
10 Node(int left, int right)
11 : left(left)
12 , right(right)
13 , s00(0)
14 , s01(0)
15 , s10(0)
16 , s11(0) {}
17};
18
19class SegmentTree {
20public:
21 vector<Node*> tree;
22
23 // Constructor: initialize segment tree with n elements
24 SegmentTree(int n)
25 : tree(n << 2) { // Allocate 4n nodes for the tree
26 build(1, 1, n);
27 }
28
29 // Build the segment tree recursively
30 void build(int nodeIndex, int left, int right) {
31 tree[nodeIndex] = new Node(left, right);
32
33 // Base case: leaf node
34 if (left == right) {
35 return;
36 }
37
38 // Recursive case: build left and right subtrees
39 int mid = (left + right) >> 1;
40 build(nodeIndex << 1, left, mid); // Build left child
41 build(nodeIndex << 1 | 1, mid + 1, right); // Build right child
42 }
43
44 // Query the maximum sum in range [left, right]
45 long long query(int nodeIndex, int queryLeft, int queryRight) {
46 // Current node is completely within query range
47 if (tree[nodeIndex]->left >= queryLeft && tree[nodeIndex]->right <= queryRight) {
48 return tree[nodeIndex]->s11;
49 }
50
51 int mid = (tree[nodeIndex]->left + tree[nodeIndex]->right) >> 1;
52 long long result = 0;
53
54 // Query only left subtree
55 if (queryRight <= mid) {
56 result = query(nodeIndex << 1, queryLeft, queryRight);
57 }
58 // Query only right subtree
59 if (queryLeft > mid) {
60 result = max(result, query(nodeIndex << 1 | 1, queryLeft, queryRight));
61 }
62
63 return result;
64 }
65
66 // Update parent node based on children's values
67 void pushup(int nodeIndex) {
68 Node* leftChild = tree[nodeIndex << 1];
69 Node* rightChild = tree[nodeIndex << 1 | 1];
70
71 // Update all four states based on children's states
72 // s00: neither endpoint selected
73 tree[nodeIndex]->s00 = max(leftChild->s00 + rightChild->s10, // Left: none, Right: left selected
74 leftChild->s01 + rightChild->s00); // Left: right selected, Right: none
75
76 // s01: right endpoint selected
77 tree[nodeIndex]->s01 = max(leftChild->s00 + rightChild->s11, // Left: none, Right: both selected
78 leftChild->s01 + rightChild->s01); // Left: right selected, Right: right selected
79
80 // s10: left endpoint selected
81 tree[nodeIndex]->s10 = max(leftChild->s10 + rightChild->s10, // Left: left selected, Right: left selected
82 leftChild->s11 + rightChild->s00); // Left: both selected, Right: none
83
84 // s11: both endpoints selected
85 tree[nodeIndex]->s11 = max(leftChild->s10 + rightChild->s11, // Left: left selected, Right: both selected
86 leftChild->s11 + rightChild->s01); // Left: both selected, Right: right selected
87 }
88
89 // Modify the value at position x to v
90 void modify(int nodeIndex, int position, int value) {
91 // Base case: reached leaf node
92 if (tree[nodeIndex]->left == tree[nodeIndex]->right) {
93 // Update s11 (element can be selected or not)
94 tree[nodeIndex]->s11 = max(0LL, (long long)value);
95 return;
96 }
97
98 // Recursive case: traverse to the target position
99 int mid = (tree[nodeIndex]->left + tree[nodeIndex]->right) >> 1;
100 if (position <= mid) {
101 modify(nodeIndex << 1, position, value); // Modify left subtree
102 } else {
103 modify(nodeIndex << 1 | 1, position, value); // Modify right subtree
104 }
105
106 // Update current node after modification
107 pushup(nodeIndex);
108 }
109
110 // Destructor: clean up allocated memory
111 ~SegmentTree() {
112 for (auto node : tree) {
113 delete node;
114 }
115 }
116};
117
118class Solution {
119public:
120 int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
121 int n = nums.size();
122 SegmentTree segTree(n);
123
124 // Initialize segment tree with original array values
125 for (int i = 0; i < n; ++i) {
126 segTree.modify(1, i + 1, nums[i]); // 1-indexed positions
127 }
128
129 long long totalSum = 0;
130 const int MOD = 1e9 + 7;
131
132 // Process each query
133 for (const auto& query : queries) {
134 // Update position query[0] with value query[1]
135 segTree.modify(1, query[0] + 1, query[1]); // Convert to 1-indexed
136
137 // Add maximum sum of non-adjacent subsequence to result
138 totalSum = (totalSum + segTree.query(1, 1, n)) % MOD;
139 }
140
141 return (int)totalSum;
142 }
143};
1441// Node structure for segment tree
2interface TreeNode {
3 left: number; // Left boundary of the interval
4 right: number; // Right boundary of the interval
5 sum00: number; // Max sum ending at even index, starting at even index
6 sum01: number; // Max sum ending at odd index, starting at even index
7 sum10: number; // Max sum ending at even index, starting at odd index
8 sum11: number; // Max sum ending at odd index, starting at odd index
9}
10
11// Global segment tree array
12let segmentTree: TreeNode[];
13
14// Build the segment tree recursively
15function build(nodeIndex: number, leftBound: number, rightBound: number): void {
16 // Initialize current node with boundaries
17 segmentTree[nodeIndex] = {
18 left: leftBound,
19 right: rightBound,
20 sum00: 0,
21 sum01: 0,
22 sum10: 0,
23 sum11: 0
24 };
25
26 // Base case: leaf node
27 if (leftBound === rightBound) {
28 return;
29 }
30
31 // Recursively build left and right subtrees
32 const mid = (leftBound + rightBound) >> 1;
33 build(nodeIndex << 1, leftBound, mid);
34 build((nodeIndex << 1) | 1, mid + 1, rightBound);
35}
36
37// Query the maximum sum in the given range
38function query(nodeIndex: number, queryLeft: number, queryRight: number): number {
39 const node = segmentTree[nodeIndex];
40
41 // Current interval is completely within query range
42 if (node.left >= queryLeft && node.right <= queryRight) {
43 return node.sum11;
44 }
45
46 const mid = (node.left + node.right) >> 1;
47 let maxSum = 0;
48
49 // Query left subtree if needed
50 if (queryRight <= mid) {
51 maxSum = query(nodeIndex << 1, queryLeft, queryRight);
52 }
53
54 // Query right subtree if needed
55 if (queryLeft > mid) {
56 maxSum = Math.max(maxSum, query((nodeIndex << 1) | 1, queryLeft, queryRight));
57 }
58
59 return maxSum;
60}
61
62// Update parent node based on children's values
63function pushup(nodeIndex: number): void {
64 const leftChild = segmentTree[nodeIndex << 1];
65 const rightChild = segmentTree[(nodeIndex << 1) | 1];
66 const current = segmentTree[nodeIndex];
67
68 // Combine left and right children to update parent
69 // sum00: even to even transition
70 current.sum00 = Math.max(
71 leftChild.sum00 + rightChild.sum10,
72 leftChild.sum01 + rightChild.sum00
73 );
74
75 // sum01: even to odd transition
76 current.sum01 = Math.max(
77 leftChild.sum00 + rightChild.sum11,
78 leftChild.sum01 + rightChild.sum01
79 );
80
81 // sum10: odd to even transition
82 current.sum10 = Math.max(
83 leftChild.sum10 + rightChild.sum10,
84 leftChild.sum11 + rightChild.sum00
85 );
86
87 // sum11: odd to odd transition
88 current.sum11 = Math.max(
89 leftChild.sum10 + rightChild.sum11,
90 leftChild.sum11 + rightChild.sum01
91 );
92}
93
94// Modify a single element in the tree
95function modify(nodeIndex: number, position: number, value: number): void {
96 const node = segmentTree[nodeIndex];
97
98 // Base case: reached leaf node
99 if (node.left === node.right) {
100 // Update leaf node with max of 0 and value (handle negative values)
101 node.sum11 = Math.max(0, value);
102 return;
103 }
104
105 // Recursively modify left or right subtree
106 const mid = (node.left + node.right) >> 1;
107 if (position <= mid) {
108 modify(nodeIndex << 1, position, value);
109 } else {
110 modify((nodeIndex << 1) | 1, position, value);
111 }
112
113 // Update current node after modification
114 pushup(nodeIndex);
115}
116
117// Main function to process queries and return sum of maximum subsequences
118function maximumSumSubsequence(nums: number[], queries: number[][]): number {
119 const arrayLength = nums.length;
120
121 // Initialize segment tree with 4 times array size
122 segmentTree = Array(arrayLength * 4);
123 build(1, 1, arrayLength);
124
125 // Initialize tree with original array values
126 for (let i = 0; i < arrayLength; i++) {
127 modify(1, i + 1, nums[i]);
128 }
129
130 let totalSum = 0;
131 const MOD = 1e9 + 7;
132
133 // Process each query
134 for (const [index, newValue] of queries) {
135 // Update element at index with new value
136 modify(1, index + 1, newValue);
137
138 // Add maximum subsequence sum to result
139 totalSum = (totalSum + query(1, 1, arrayLength)) % MOD;
140 }
141
142 return totalSum;
143}
144Time and Space Complexity
Time Complexity: O((n + q) × log n)
The time complexity breaks down as follows:
- Building the segment tree: The
buildmethod is called once during initialization and visits each node in the tree exactly once. Since there areO(n)nodes in the segment tree, building takesO(n)time. - Initial modifications: The code performs
ninitialmodifyoperations to populate the tree with values fromnums. Eachmodifyoperation traverses from root to leaf, which isO(log n)depth, and callspushupon the way back up, alsoO(log n). So initial setup isO(n × log n). - Processing queries: For each of the
qqueries, the code performs:- One
modifyoperation:O(log n) - One
queryoperation:O(log n) - Total per query:
O(log n) - Total for all queries:
O(q × log n)
- One
Overall time complexity: O(n + n × log n + q × log n) = O((n + q) × log n)
Space Complexity: O(n)
The space complexity is determined by:
- Segment tree storage: The tree is initialized with
n << 2(which is4n) nodes to ensure sufficient space for a complete binary tree structure. Each node stores a constant amount of data (two integers and four values for dynamic programming states). - Auxiliary space: The recursive calls in
build,modify, andqueryuseO(log n)stack space due to the tree height.
Since O(4n) + O(log n) = O(n), the overall space complexity is O(n).
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Incorrect State Initialization for Leaf Nodes
Pitfall: A common mistake is incorrectly initializing the four states (s00, s01, s10, s11) for leaf nodes. Developers often set all states to the node value or forget to handle negative values properly.
Incorrect Implementation:
def modify(self, node_idx: int, position: int, value: int) -> None:
current_node = self.tree[node_idx]
if current_node.left == current_node.right:
# WRONG: Setting all states to value
current_node.s00 = value
current_node.s01 = value
current_node.s10 = value
current_node.s11 = value
return
Why it's wrong: For a leaf node representing a single element:
- s00 means we don't take the element (should be 0)
- s01 means we take the element as right boundary only (impossible for single element)
- s10 means we take the element as left boundary only (impossible for single element)
- s11 means we take the element (should be max(0, value) to handle negatives)
Correct Implementation:
def modify(self, node_idx: int, position: int, value: int) -> None:
current_node = self.tree[node_idx]
if current_node.left == current_node.right:
# Correct: Only s11 is meaningful for a leaf
current_node.s00 = 0 # Don't take the element
current_node.s01 = 0 # Can't have only right boundary
current_node.s10 = 0 # Can't have only left boundary
current_node.s11 = max(0, value) # Either take it (if positive) or skip
return
2. Incorrect Pushup Logic for Combining States
Pitfall: Mixing up the state combinations when merging child nodes, especially forgetting the adjacency constraint between the right endpoint of the left child and the left endpoint of the right child.
Incorrect Implementation:
def pushup(self, node_idx: int) -> None:
left_child = self.tree[node_idx << 1]
right_child = self.tree[node_idx << 1 | 1]
current_node = self.tree[node_idx]
# WRONG: Allowing adjacent elements to be selected
current_node.s11 = left_child.s11 + right_child.s11 # This would select adjacent elements!
Why it's wrong: If we take s11 from the left child (which includes its right boundary) and s11 from the right child (which includes its left boundary), we're selecting two adjacent elements in the original array.
Correct Implementation:
def pushup(self, node_idx: int) -> None:
left_child = self.tree[node_idx << 1]
right_child = self.tree[node_idx << 1 | 1]
current_node = self.tree[node_idx]
# Correct: Ensure no adjacent elements are selected
current_node.s11 = max(
left_child.s10 + right_child.s11, # Left excludes its right, right includes both
left_child.s11 + right_child.s01 # Left includes both, right excludes its left
)
3. Off-by-One Errors with Indexing
Pitfall: Confusion between 0-indexed input array and 1-indexed segment tree implementation.
Incorrect Implementation:
def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
n = len(nums)
segment_tree = SegmentTree(n)
# WRONG: Using 0-indexed directly
for i, value in enumerate(nums):
segment_tree.modify(1, i, value) # Should be i+1
for index, new_value in queries:
segment_tree.modify(1, index, new_value) # Should be index+1
Correct Implementation:
def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
n = len(nums)
segment_tree = SegmentTree(n)
# Correct: Convert to 1-indexed
for i, value in enumerate(nums, 1): # Start from 1
segment_tree.modify(1, i, value)
for index, new_value in queries:
segment_tree.modify(1, index + 1, new_value) # Add 1 to convert
4. Not Handling Negative Values Properly
Pitfall: Forgetting that we can choose to skip negative elements entirely, leading to suboptimal solutions.
Solution: Always use max(0, value) for leaf nodes and ensure the state transitions allow for skipping elements entirely. The four-state design naturally handles this when implemented correctly.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is
[3, 7, 40, 80].
What is the recurrence relation?
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
https assets algo monster cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger problem using the solutions
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Want a Structured Path to Master System Design Too? Don’t Miss This!