Segment Tree AC solution, who can help me analyze big O?


  • 0

    I got the Segment Tree solution, it got AC, but the run time is more than 400ms. I'm really confused what's the time complexity of this solution. Who can help me analyze? I really do appreciate it!
    My thought is imagine the matrix as a three dimension, using middle point to cut the plane figure into 4 sub matrixs
    0_1484841596217_st2.jpeg
    The code logic is very simple, build tree will take m*n time. But I'm not sure update() and query() take how much time, is anyone can give me some hint? I really do appreciate it!

    public class NumMatrix {
        class TreeNode {
            int x1, y1, x2, y2, sum;
            TreeNode t1, t2, t3, t4;
            public TreeNode(int x1, int y1, int x2, int y2) {
                this.x1 = x1;
                this.y1 = y1;
                this.x2 = x2;
                this.y2 = y2;
            }
        }
        TreeNode root;
        private TreeNode build(int[][] A, int x1, int y1, int x2, int y2) {
            if (x1 > x2 || y1 > y2) return null;
            if (x1 == x2 && y1 == y2) {
                TreeNode node = new TreeNode(x1, y1, x2, y2);
                node.sum = A[x1][y1];
                return node;
            }
            int rowMid = x1 + (x2 - x1) / 2;
            int colMid = y1 + (y2 - y1) / 2;
            TreeNode root = new TreeNode(x1, y1, x2, y2);
            root.t1 = build(A, x1, y1, rowMid, colMid);
            root.t2 = build(A, x1, colMid + 1, rowMid, y2);
            root.t3 = build(A, rowMid + 1, y1, x2, colMid);
            root.t4 = build(A, rowMid + 1, colMid + 1, x2, y2);
            root.sum = (root.t1 == null ? 0 : root.t1.sum) +
                        (root.t2 == null ? 0 : root.t2.sum) +
                        (root.t3 == null ? 0 : root.t3.sum) +
                        (root.t4 == null ? 0 : root.t4.sum);
            return root;
        }
    
        private int query(TreeNode root, int x1, int y1, int x2, int y2) {
            if (root == null || x1 > root.x2 || y1 > root.y2 || x2 < root.x1 || y2 < root.y1) return 0;
            if (x1 <= root.x1 && y1 <= root.y1 && x2 >= root.x2 && y2 >= root.y2) return root.sum;
            return query(root.t1, x1, y1, x2, y2) + query(root.t2, x1, y1, x2, y2) +
                        query(root.t3, x1, y1, x2, y2) + query(root.t4, x1, y1, x2, y2);
        }
    
        private void update(TreeNode root, int x, int y, int val) {
            if (root == null || x < root.x1 || x > root.x2 || y < root.y1 || y > root.y2) return;
            if (x == root.x1 && x == root.x2 && y == root.y1 && y == root.y2) {
                root.sum = val;
                return;
            }
            update(root.t1, x, y, val);
            update(root.t2, x, y, val);
            update(root.t3, x, y, val);
            update(root.t4, x, y, val);
            root.sum = (root.t1 == null ? 0 : root.t1.sum) +
                    (root.t2 == null ? 0 : root.t2.sum) +
                    (root.t3 == null ? 0 : root.t3.sum) +
                    (root.t4 == null ? 0 : root.t4.sum);
        }    
        
    
        public NumMatrix(int[][] matrix) {
            if (matrix == null || matrix.length == 0) return;
            root = build(matrix, 0, 0, matrix.length - 1, matrix[0].length - 1);
        }
    
        public void update(int row, int col, int val) {
            update(root, row, col, val);
        }
    
        public int sumRegion(int row1, int col1, int row2, int col2) {
            return query(root, row1, col1, row2, col2);
        }
    }
    

    I don't know if my analysis is correct, please correct me if someone have solution!
    I simply think the length and width are same, N
    if length=2, it will have 4 sub matrixs, and total depth/layer/height will be 2
    if length=4, the total depth will be 3
    if length=8, the total depth will be 4
    if length=16, the total depth will be 5
    So I think if length=N, the total depth will be logN + 1
    so logN might be the time complexity. Am I correct?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.