1/**
2 * Binary Indexed Tree (Fenwick Tree) implementation for efficient prefix sum queries and updates
3 */
4class BinaryIndexedTree {
5    private int size;
6    private int[] tree;
7
8    /**
9     * Initialize a Binary Indexed Tree with given size
10     * @param size the size of the array to be represented
11     */
12    public BinaryIndexedTree(int size) {
13        this.size = size;
14        // BIT uses 1-based indexing, so we need size + 1 elements
15        this.tree = new int[size + 1];
16    }
17
18    /**
19     * Update the value at position index by adding delta
20     * @param index the 1-based position to update
21     * @param delta the value to add at the position
22     */
23    public void update(int index, int delta) {
24        // Propagate the update up the tree
25        while (index <= size) {
26            tree[index] += delta;
27            // Move to the next node that this index affects
28            index += lowbit(index);
29        }
30    }
31
32    /**
33     * Query the prefix sum from index 1 to index (inclusive)
34     * @param index the 1-based ending position for the sum
35     * @return the prefix sum from 1 to index
36     */
37    public int query(int index) {
38        int sum = 0;
39        // Accumulate values while traversing down the tree
40        while (index > 0) {
41            sum += tree[index];
42            // Move to the parent node in the tree
43            index -= lowbit(index);
44        }
45        return sum;
46    }
47
48    /**
49     * Get the lowest set bit of a number
50     * This determines the range of responsibility for each node in the BIT
51     * @param x the input number
52     * @return the value of the lowest set bit
53     */
54    public static int lowbit(int x) {
55        return x & -x;
56    }
57}
58
59/**
60 * 2D Matrix with efficient range sum queries and single element updates
61 * Uses Binary Indexed Trees for each row
62 */
63class NumMatrix {
64    private BinaryIndexedTree[] rowTrees;
65
66    /**
67     * Initialize the matrix with given values
68     * Creates a Binary Indexed Tree for each row
69     * @param matrix the initial 2D matrix values
70     */
71    public NumMatrix(int[][] matrix) {
72        int numRows = matrix.length;
73        int numCols = matrix[0].length;
74      
75        // Create a BIT for each row
76        rowTrees = new BinaryIndexedTree[numRows];
77      
78        for (int row = 0; row < numRows; row++) {
79            BinaryIndexedTree currentRowTree = new BinaryIndexedTree(numCols);
80          
81            // Initialize the BIT with values from the matrix row
82            for (int col = 0; col < numCols; col++) {
83                // BIT uses 1-based indexing, so we use col + 1
84                currentRowTree.update(col + 1, matrix[row][col]);
85            }
86          
87            rowTrees[row] = currentRowTree;
88        }
89    }
90
91    /**
92     * Update a single element in the matrix
93     * @param row the row index (0-based)
94     * @param col the column index (0-based)
95     * @param val the new value to set
96     */
97    public void update(int row, int col, int val) {
98        BinaryIndexedTree currentRowTree = rowTrees[row];
99      
100        // Calculate the current value at matrix[row][col]
101        // This is done by querying the range sum from col to col (single element)
102        int currentValue = currentRowTree.query(col + 1) - currentRowTree.query(col);
103      
104        // Update with the difference between new and old value
105        currentRowTree.update(col + 1, val - currentValue);
106    }
107
108    /**
109     * Calculate the sum of elements in the rectangle defined by the corners
110     * @param row1 top row index (0-based, inclusive)
111     * @param col1 left column index (0-based, inclusive)
112     * @param row2 bottom row index (0-based, inclusive)
113     * @param col2 right column index (0-based, inclusive)
114     * @return the sum of all elements in the specified rectangle
115     */
116    public int sumRegion(int row1, int col1, int row2, int col2) {
117        int totalSum = 0;
118      
119        // Sum the range for each row in the rectangle
120        for (int row = row1; row <= row2; row++) {
121            BinaryIndexedTree currentRowTree = rowTrees[row];
122          
123            // Get sum from col1 to col2 (inclusive) using prefix sums
124            // Sum[col1, col2] = PrefixSum[col2] - PrefixSum[col1 - 1]
125            totalSum += currentRowTree.query(col2 + 1) - currentRowTree.query(col1);
126        }
127      
128        return totalSum;
129    }
130}
131
132/**
133 * Your NumMatrix object will be instantiated and called as such:
134 * NumMatrix obj = new NumMatrix(matrix);
135 * obj.update(row,col,val);
136 * int param_2 = obj.sumRegion(row1,col1,row2,col2);
137 */
138

1class BinaryIndexedTree {
2public:
3    int size;                    // Size of the array (1-indexed)
4    vector<int> tree;            // Fenwick tree array
5  
6    // Constructor: Initialize BIT with given size
7    BinaryIndexedTree(int n) : size(n), tree(n + 1) {}
8  
9    // Update the value at index by adding delta
10    // Time complexity: O(log n)
11    void update(int index, int delta) {
12        while (index <= size) {
13            tree[index] += delta;
14            index += lowbit(index);  // Move to next node that needs update
15        }
16    }
17  
18    // Query prefix sum from index 1 to index
19    // Time complexity: O(log n)
20    int query(int index) {
21        int sum = 0;
22        while (index > 0) {
23            sum += tree[index];
24            index -= lowbit(index);  // Move to parent node
25        }
26        return sum;
27    }
28  
29    // Get the lowest set bit of x
30    // Example: lowbit(6) = 2 (binary: 110 -> 010)
31    int lowbit(int x) {
32        return x & -x;
33    }
34};
35
36class NumMatrix {
37public:
38    vector<BinaryIndexedTree*> rowTrees;  // One BIT for each row
39  
40    // Constructor: Build BIT for each row of the matrix
41    // Time complexity: O(m * n * log n)
42    NumMatrix(vector<vector<int>>& matrix) {
43        int numRows = matrix.size();
44        int numCols = matrix[0].size();
45        rowTrees.resize(numRows);
46      
47        // Create a BIT for each row
48        for (int row = 0; row < numRows; ++row) {
49            BinaryIndexedTree* tree = new BinaryIndexedTree(numCols);
50            // Initialize each BIT with the row's values
51            for (int col = 0; col < numCols; ++col) {
52                tree->update(col + 1, matrix[row][col]);  // BIT uses 1-indexed
53            }
54            rowTrees[row] = tree;
55        }
56    }
57  
58    // Update matrix[row][col] to val
59    // Time complexity: O(log n)
60    void update(int row, int col, int val) {
61        BinaryIndexedTree* tree = rowTrees[row];
62        // Calculate current value at (row, col)
63        int currentVal = tree->query(col + 1) - tree->query(col);
64        // Update with the difference
65        tree->update(col + 1, val - currentVal);
66    }
67  
68    // Calculate sum of rectangle from (row1, col1) to (row2, col2)
69    // Time complexity: O(m * log n) where m is number of rows in range
70    int sumRegion(int row1, int col1, int row2, int col2) {
71        int totalSum = 0;
72        // Sum up each row's contribution
73        for (int row = row1; row <= row2; ++row) {
74            BinaryIndexedTree* tree = rowTrees[row];
75            // Range sum = prefixSum(col2) - prefixSum(col1-1)
76            totalSum += tree->query(col2 + 1) - tree->query(col1);
77        }
78        return totalSum;
79    }
80};
81
82/**
83 * Your NumMatrix object will be instantiated and called as such:
84 * NumMatrix* obj = new NumMatrix(matrix);
85 * obj->update(row,col,val);
86 * int param_2 = obj->sumRegion(row1,col1,row2,col2);
87 */
88

1// Binary Indexed Tree (Fenwick Tree) implementation
2let size: number;                    // Size of the array (1-indexed)
3let tree: number[];                  // Fenwick tree array
4
5// Initialize BIT with given size
6function initBIT(n: number): void {
7    size = n;
8    tree = new Array(n + 1).fill(0);
9}
10
11// Get the lowest set bit of x
12// Example: lowbit(6) = 2 (binary: 110 -> 010)
13function lowbit(x: number): number {
14    return x & -x;
15}
16
17// Update the value at index by adding delta
18// Time complexity: O(log n)
19function updateBIT(index: number, delta: number): void {
20    while (index <= size) {
21        tree[index] += delta;
22        index += lowbit(index);  // Move to next node that needs update
23    }
24}
25
26// Query prefix sum from index 1 to index
27// Time complexity: O(log n)
28function queryBIT(index: number): number {
29    let sum = 0;
30    while (index > 0) {
31        sum += tree[index];
32        index -= lowbit(index);  // Move to parent node
33    }
34    return sum;
35}
36
37// NumMatrix implementation using Binary Indexed Trees
38let rowTrees: { size: number; tree: number[] }[];  // One BIT for each row
39
40// Constructor: Build BIT for each row of the matrix
41// Time complexity: O(m * n * log n)
42function NumMatrix(matrix: number[][]): void {
43    const numRows = matrix.length;
44    const numCols = matrix[0].length;
45    rowTrees = [];
46  
47    // Create a BIT for each row
48    for (let row = 0; row < numRows; row++) {
49        // Create a new BIT for this row
50        const rowTree = {
51            size: numCols,
52            tree: new Array(numCols + 1).fill(0)
53        };
54      
55        // Initialize the BIT with the row's values
56        for (let col = 0; col < numCols; col++) {
57            // Update BIT at position col + 1 (BIT uses 1-indexed)
58            let idx = col + 1;
59            while (idx <= numCols) {
60                rowTree.tree[idx] += matrix[row][col];
61                idx += lowbit(idx);
62            }
63        }
64      
65        rowTrees.push(rowTree);
66    }
67}
68
69// Update matrix[row][col] to val
70// Time complexity: O(log n)
71function update(row: number, col: number, val: number): void {
72    const rowTree = rowTrees[row];
73  
74    // Calculate current value at (row, col) using range query
75    // Current value = prefixSum(col + 1) - prefixSum(col)
76    let currentVal = 0;
77    let idx = col + 1;
78    while (idx > 0) {
79        currentVal += rowTree.tree[idx];
80        idx -= lowbit(idx);
81    }
82    idx = col;
83    while (idx > 0) {
84        currentVal -= rowTree.tree[idx];
85        idx -= lowbit(idx);
86    }
87  
88    // Update with the difference between new value and current value
89    const delta = val - currentVal;
90    idx = col + 1;
91    while (idx <= rowTree.size) {
92        rowTree.tree[idx] += delta;
93        idx += lowbit(idx);
94    }
95}
96
97// Calculate sum of rectangle from (row1, col1) to (row2, col2)
98// Time complexity: O(m * log n) where m is number of rows in range
99function sumRegion(row1: number, col1: number, row2: number, col2: number): number {
100    let totalSum = 0;
101  
102    // Sum up each row's contribution
103    for (let row = row1; row <= row2; row++) {
104        const rowTree = rowTrees[row];
105      
106        // Calculate range sum for this row
107        // Range sum = prefixSum(col2 + 1) - prefixSum(col1)
108        let rowSum = 0;
109      
110        // Add prefixSum(col2 + 1)
111        let idx = col2 + 1;
112        while (idx > 0) {
113            rowSum += rowTree.tree[idx];
114            idx -= lowbit(idx);
115        }
116      
117        // Subtract prefixSum(col1)
118        idx = col1;
119        while (idx > 0) {
120            rowSum -= rowTree.tree[idx];
121            idx -= lowbit(idx);
122        }
123      
124        totalSum += rowSum;
125    }
126  
127    return totalSum;
128}
129
130/**
131 * Your NumMatrix object will be instantiated and called as such:
132 * NumMatrix(matrix);
133 * update(row, col, val);
134 * let sum = sumRegion(row1, col1, row2, col2);
135 */
136