🚀 Segment Tree for Maximum Sum Subsequence
🚀 Segment Tree for Maximum Sum SubsequenceIntuitionThe problem asks us to handle a series of updates on an array and compute the maximum sum subsequence for eac
# 🚀 Segment Tree for Maximum Sum Subsequence

## Intuition
The problem asks us to handle a series of updates on an array and compute the maximum sum subsequence for each update. A straightforward approach could involve recalculating the subsequence after each update, but this would be inefficient. Instead, we use a **Segment Tree** to efficiently update values and calculate maximum subsequences, leveraging dynamic programming (DP) within the tree.

## Approach

### Key Concepts
We build a **Segment Tree** where each node stores 4 values representing the different states of a subsequence:

- **dp00**: The maximum sum when no element is taken from this segment.
- **dp10**: The maximum sum when the last element is taken from this segment, but the previous element is not.
- **dp01**: The maximum sum when the previous element is taken from this segment, but the last one is not.
- **dp11**: The maximum sum when both elements are taken from this segment.

We recursively build the tree by dividing the input array into smaller segments. The **merge step** combines two child nodes by recalculating their DP values based on possible transitions. The solution involves applying the updates, recalculating the DP values, and keeping track of the maximum subsequence sum.

### Step-by-Step Breakdown
1. **Build the Tree**: Start by constructing the segment tree with the given array.
2. **Process Updates**: For each query, update the segment tree and calculate the maximum subsequence sum.
3. **Modulo Operation**: Since the result can be large, every result is taken modulo \(10^9 + 7\).

### Segment Tree Node Structure
Each node contains:
- Four DP values (`dp00`, `dp10`, `dp01`, `dp11`) representing different states of subsequences.
- The range it covers (`minIdx` and `maxIdx`).
- Two child nodes (`left` and `right`).

### Solution Flow
- **Build the Tree**: Start by constructing the segment tree with the given array.
- **Process Updates**: For each query, update the segment tree and calculate the maximum subsequence sum.
- **Modulo Operation**: Since the result can be large, every result is taken modulo \(10^9 + 7\).

___
# Code
```java []
class Solution {

    final static long MOD = 1000000007; // Define the modulo constant

    class SegNode {
        long dp00;
        long dp10;
        long dp01;
        long dp11;
        int minIdx;
        int maxIdx;
        SegNode left;
        SegNode right;

        public long maxValue() {
            return Math.max(Math.max(dp00, dp10), Math.max(dp01, dp11));
        }
    }

    SegNode update(SegNode node, int i, int v) {
        if (node.minIdx == node.maxIdx && node.maxIdx == i) {
            // Update the value at the leaf node
            node.dp11 = v;
            return node;
        }
        int mid = node.minIdx + (node.maxIdx - node.minIdx) / 2;

        if (i <= mid) {
            node.left = update(node.left, i, v); // Update the left child
        } else {
            node.right = update(node.right, i, v); // Update the right child
        }

        // Recalculate the dp values after the update
        node.dp00 = max(node.left.dp00 + node.right.dp00, node.left.dp01 + node.right.dp00, node.left.dp00 + node.right.dp10);
        node.dp10 = max(node.left.dp10 + node.right.dp00, node.left.dp11 + node.right.dp00, node.left.dp10 + node.right.dp10);
        node.dp01 = max(node.left.dp00 + node.right.dp01, node.left.dp01 + node.right.dp01, node.left.dp00 + node.right.dp11);
        node.dp11 = max(node.left.dp10 + node.right.dp01, node.left.dp11 + node.right.dp01, node.left.dp10 + node.right.dp11);

        return node;
    }

    SegNode build(int[] nums, int left, int right) {
        if (left == right) {
            SegNode leaf = new SegNode();
            leaf.dp00 = 0;
            leaf.dp10 = 0;
            leaf.dp01 = 0;
            leaf.dp11 = nums[left]; // Set the value at the leaf node
            leaf.minIdx = left;
            leaf.maxIdx = right;
            return leaf;
        }

        int mid = left + (right - left) / 2;
        SegNode node = new SegNode();
        node.left = build(nums, left, mid);
        node.right = build(nums, mid + 1, right);
        node.minIdx = left;
        node.maxIdx = right;

        // Recalculate the dp values for the internal node
        node.dp00 = max(node.left.dp00 + node.right.dp00, node.left.dp01 + node.right.dp00, node.left.dp00 + node.right.dp10);
        node.dp10 = max(node.left.dp10 + node.right.dp00, node.left.dp11 + node.right.dp00, node.left.dp10 + node.right.dp10);
        node.dp01 = max(node.left.dp00 + node.right.dp01, node.left.dp01 + node.right.dp01, node.left.dp00 + node.right.dp11);
        node.dp11 = max(node.left.dp10 + node.right.dp01, node.left.dp11 + node.right.dp01, node.left.dp10 + node.right.dp11);

        return node;
    }

    long max(long v1, long v2, long v3) {
        return Math.max(Math.max(v1, v2), v3);
    }

    public int maximumSumSubsequence(int[] nums, int[][] queries) {
        long res = 0;
        SegNode root = build(nums, 0, nums.length - 1); // Build the segment tree
        for (int[] q : queries) {
            update(root, q[0], q[1]); // Apply each update from the queries
            res += root.maxValue();
            res %= MOD;
        }

        // Return the final result after all updates, applying modulo
        return (int) res;
    }
}

```
['Java']