Given an array of n elements arr_1, arr_2, ..., arr_n, support q operations:

1. Type 1: Update arr_x = value
2. Type 2: Query maximum subarray sum in range [l, r]

Information to Maintain

To solve this problem using divide and conquer, we need to determine what information can be merged to compute the required result.

The maximum subarray sum in a range [l, r] can be one of three cases:

1. Completely within left half: [l, mid]
2. Completely within right half: [mid + 1, r]
3. Crossing the midpoint: combination of suffix from left half and prefix from right half

For complete solution, we need to maintain four values for each segment:

• Maximum subarray sum
• Maximum prefix sum
• Maximum suffix sum
• Total sum

Merge Logic

When combining two segments (left and right):

• Maximum subarray sum: max of left max sum, right max sum, or combined cross sum
• Maximum prefix: max of left prefix or left total plus right prefix
• Maximum suffix: max of right suffix or right total plus left suffix
• Total sum: sum of both segments

struct SegmentData {
    long long max_subarray_sum;
    long long max_prefix_sum;
    long long max_suffix_sum;
    long long total_sum;
};

struct TreeNode {
    SegmentData data;
} tree[N * 4];

SegmentData combine(const SegmentData& left, const SegmentData& right) {
    SegmentData result;
    result.max_subarray_sum = std::max({left.max_subarray_sum, 
                                      right.max_subarray_sum, 
                                      left.max_suffix_sum + right.max_prefix_sum});
    result.max_prefix_sum = std::max(left.max_prefix_sum, 
                                    left.total_sum + right.max_prefix_sum);
    result.max_suffix_sum = std::max(right.max_suffix_sum, 
                                    left.max_suffix_sum + right.total_sum);
    result.total_sum = left.total_sum + right.total_sum;
    return result;
}

void refresh_node(int node_id) {
    tree[node_id].data = combine(tree[node_id * 2].data, 
                                tree[node_id * 2 + 1].data);
}

Main Program Structure

int main() {
    int size, queries;
    std::cin >> size >> queries;
    for (int i = 1; i <= size; i++) {
        std::cin >> input_array[i];
    }
    
    build_tree(1, 1, size);
    
    for (int i = 1; i <= queries; i++) {
        int operation_type;
        std::cin >> operation_type;
        
        if (operation_type == 1) {
            int position, new_value;
            std::cin >> position >> new_value;
            update_single(1, 1, size, position, new_value);
        } else {
            int left_bound, right_bound;
            std::cin >> left_bound >> right_bound;
            auto result = fetch_range(1, 1, size, left_bound, right_bound);
            std::cout << result.max_subarray_sum << '\n';
        }
    }
    return 0;
}

Core Operations Implementation

void build_tree(int node_id, int start, int end) {
    if (start == end) {
        tree[node_id].data = {input_array[start], 
                             input_array[start], 
                             input_array[start], 
                             input_array[start]};
    } else {
        int middle = (start + end) / 2;
        build_tree(node_id * 2, start, middle);
        build_tree(node_id * 2 + 1, middle + 1, end);
        refresh_node(node_id);
    }
}

SegmentData fetch_range(int node_id, int start, int end, int query_start, int query_end) {
    if (start == query_start && end == query_end) {
        return tree[node_id].data;
    } else {
        int middle = (start + end) / 2;
        if (query_end <= middle) {
            return fetch_range(node_id * 2, start, middle, query_start, query_end);
        } else if (query_start > middle) {
            return fetch_range(node_id * 2 + 1, middle + 1, end, query_start, query_end);
        } else {
            return combine(fetch_range(node_id * 2, start, middle, query_start, middle),
                          fetch_range(node_id * 2 + 1, middle + 1, end, middle + 1, query_end));
        }
    }
}

void update_single(int node_id, int start, int end, int position, int value) {
    if (start == end) {
        tree[node_id].data = {value, value, value, value};
    } else {
        int middle = (start + end) / 2;
        if (position <= middle) {
            update_single(node_id * 2, start, middle, position, value);
        } else {
            update_single(node_id * 2 + 1, middle + 1, end, position, value);
        }
        refresh_node(node_id);
    }
}

Complete Solution

#include <bits/stdc++.h>

const int N = 200005;
int input_array[N];

struct SegmentData {
    long long max_subarray_sum;
    long long max_prefix_sum;
    long long max_suffix_sum;
    long long total_sum;
};

struct TreeNode {
    SegmentData data;
} tree[N * 4];

SegmentData combine(const SegmentData& left, const SegmentData& right) {
    SegmentData result;
    result.max_subarray_sum = std::max({left.max_subarray_sum, 
                                      right.max_subarray_sum, 
                                      left.max_suffix_sum + right.max_prefix_sum});
    result.max_prefix_sum = std::max(left.max_prefix_sum, 
                                    left.total_sum + right.max_prefix_sum);
    result.max_suffix_sum = std::max(right.max_suffix_sum, 
                                    left.max_suffix_sum + right.total_sum);
    result.total_sum = left.total_sum + right.total_sum;
    return result;
}

void refresh_node(int node_id) {
    tree[node_id].data = combine(tree[node_id * 2].data, 
                                tree[node_id * 2 + 1].data);
}

void build_tree(int node_id, int start, int end) {
    if (start == end) {
        tree[node_id].data = {input_array[start], 
                             input_array[start], 
                             input_array[start], 
                             input_array[start]};
    } else {
        int middle = (start + end) / 2;
        build_tree(node_id * 2, start, middle);
        build_tree(node_id * 2 + 1, middle + 1, end);
        refresh_node(node_id);
    }
}

SegmentData fetch_range(int node_id, int start, int end, int query_start, int query_end) {
    if (start == query_start && end == query_end) {
        return tree[node_id].data;
    } else {
        int middle = (start + end) / 2;
        if (query_end <= middle) {
            return fetch_range(node_id * 2, start, middle, query_start, query_end);
        } else if (query_start > middle) {
            return fetch_range(node_id * 2 + 1, middle + 1, end, query_start, query_end);
        } else {
            return combine(fetch_range(node_id * 2, start, middle, query_start, middle),
                          fetch_range(node_id * 2 + 1, middle + 1, end, middle + 1, query_end));
        }
    }
}

void update_single(int node_id, int start, int end, int position, int value) {
    if (start == end) {
        tree[node_id].data = {value, value, value, value};
    } else {
        int middle = (start + end) / 2;
        if (position <= middle) {
            update_single(node_id * 2, start, middle, position, value);
        } else {
            update_single(node_id * 2 + 1, middle + 1, end, position, value);
        }
        refresh_node(node_id);
    }
}

int main() {
    int size, queries;
    std::cin >> size >> queries;
    for (int i = 1; i <= size; i++) {
        std::cin >> input_array[i];
    }
    
    build_tree(1, 1, size);
    
    for (int i = 1; i <= queries; i++) {
        int operation_type;
        std::cin >> operation_type;
        
        if (operation_type == 1) {
            int position, new_value;
            std::cin >> position >> new_value;
            update_single(1, 1, size, position, new_value);
        } else {
            int left_bound, right_bound;
            std::cin >> left_bound >> right_bound;
            auto result = fetch_range(1, 1, size, left_bound, right_bound);
            std::cout << result.max_subarray_sum << '\n';
        }
    }
    return 0;
}