Range Sum Query - Mutable -leetcode

이 문 제 는 내 가 이전에 만 든 RangeSum 의 1 차원 형식의 또 다른 변종 이다.이번 에는 공간 적 으로 1 차원 이지 만 그 시간 에 수정 을 해서 문제 의 해결 방향 이 바 뀌 었 고 오히려 제 가 처음에 문 제 를 풀 때 생각 했 던 특정한 라인 의 길 이 를 빨리 구 하 는 생각 으로 돌 아 왔 습 니 다.
새로운 것 이나 내 가 아직 잘 모 르 는 데이터 구 조 를 도입 했다.
SegmentTree。선분 수 또는 구간 수 라 고도 부른다.사실 구간 수 라 고 부 르 는 게 더 이해 가 돼 요.나무: 한 그루 의 나무 이 고 두 갈래 의 나무 입 니 다.선분: 나무의 모든 노드 는 하나의 선분 (또는 '구간' 이 라 고 부 르 는 것 이 더 > 이해 하기 쉽 고 구간 의 출발점 과 종점 은 보통 정수) 과 같은 층 의 노드 가 대표 하 는 구간 에 대응 하여 서로 겹 치지 않 습 니 다.잎 노드 의 구간 은 단위 길이 여서 더 이상 나 눌 수 없다.
선분 나 무 는 이 진 트 리 로 나무의 모든 결점 은 하나의 구간 [a, b] 을 나타 낸다.a, b 는 보통 정수 입 니 다.모든 잎 노드 는 단위 구간 을 표시 한다.모든 비 엽 결점 이 표시 하 는 결점 [a, b] 에 대해 왼쪽 아들 이 표시 하 는 구간 은 [a, (a + b) / 2] 이 고 오른쪽 아들 이 표시 하 는 구간 은 [(a + b) / 2, b] (나눗셈 제거) 이다.
선분 트 리 의 기본 용도: 선분 트 리 는 구간 통계 와 관련 된 문제 에 적합 합 니 다. 예 를 들 어 일부 데 이 터 는 구간 에 따라 구분 할 수 있 고 구간 동태 에 따라 수정 할 수 있 으 며 구간 에 따라 여러 번 조회 해 야 합 니 다. 그러면 선분 트 리 를 사용 하면 비교적 빠 른 조회 속 도 를 얻 을 수 있 습 니 다.
선분 트 리 의 구축 createSeg / / 노드 v 를 뿌리 로 트 리 를 만 들 고 v 대응 구간 은 [l, r] {노드 v 에 대한 초기 화 if (l! = r) {v 의 왼쪽 아 이 를 뿌리 로 트 리 를 만 들 고 구간 은 [l, (l + r) / 2] v 의 오른쪽 아 이 를 뿌리 로 트 리 를 만 들 고 구간 은 [(l + r) / 2 + 1, r]}}}} 이 문 제 는 제 가 원래 의 방법 을 사용 하여 시간 복잡 도의 요 구 를 만족 시 키 지 못 하고 토론 구역 에 따라 정 리 된 답 입 니 다.
다음은 leetcode 에서 토론 구 의 한 네티즌 의 코드 입 니 다.

public class NumArray {

    class SegmentTreeNode {
        int start, end;
        SegmentTreeNode left, right;
        int sum;

        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
            this.left = null;
            this.right = null;
            this.sum = 0;
        }
    }//      ，           。         。

    SegmentTreeNode root = null;//    ，     

    public NumArray(int[] nums) {
        root = buildTree(nums, 0, nums.length-1);//    
    }

    private SegmentTreeNode buildTree(int[] nums, int start, int end) {
        if (start > end) {//      ，     
            return null;
        } else {
            SegmentTreeNode ret = new SegmentTreeNode(start, end);//             
            if (start == end) {//         start end        ，      。      ， sum          nums[start]。
                ret.sum = nums[start];
            } else {
                int mid = start  + (end - start) / 2;//          ，               。 
                ret.left = buildTree(nums, start, mid);
                ret.right = buildTree(nums, mid + 1, end);
                ret.sum = ret.left.sum + ret.right.sum;
            }         
            return ret;
        }
    }

    void update(int i, int val) {
        update(root, i, val);
    }

    void update(SegmentTreeNode root, int pos, int val) {
        if (root.start == root.end) {//      ，    ，          。
           root.sum = val;
        } else {
            int mid = root.start + (root.end - root.start) / 2;
            if (pos <= mid) {
                 update(root.left, pos, val);
            } else {
                 update(root.right, pos, val);
            }
            root.sum = root.left.sum + root.right.sum;//    sum         。
        }
    }

    public int sumRange(int i, int j) {
        return sumRange(root, i, j);
    }

    public int sumRange(SegmentTreeNode root, int start, int end) {
        if (root.end == end && root.start == start) {//                ，    
            return root.sum;
        } else {//         ，    
            int mid = root.start + (root.end - root.start) / 2;
            if (end <= mid) {//      
                return sumRange(root.left, start, end);
            } else if (start >= mid+1) {//      
                return sumRange(root.right, start, end);
            }  else {   //        ，                    。
                return sumRange(root.right, mid+1, end) + sumRange(root.left, start, mid);
            }
        }
    }

내 가 다시 쓴 코드 는 한 번 에 한 번 debug 를 거 쳐 다른 사람의 한 줄 에 한 줄 씩 두 번 더 보고 나 서 야 다 보 았 다. 조금의 의미 도 다 르 게 해 서 는 안 된다. 이것 이 바로 프로그램 이다.

public class NumArray {

    private class Node{//tree node
        Node left,right;//left and right child
        int start,end;  //the range charged by the node
        int sum;        //sum of the range charged by the node
       public Node(){
            left=right=null;
            sum=0;
        }
    }
    Node root=null;          //root of the the tree for this problem
    public NumArray(int[] nums) {//in this function, we shoule create a tree to hold all elements in nums and calc sum.which achieved by recursion.
        int length=nums.length;     
        root=makeATree(nums,0,length-1);
    }
    private Node makeATree(int[] nums,int start,int end){
        if(start>end){return null;}
        Node tree=new Node();
        tree.start=start;
        tree.end=end;
        if(start==end){
            tree.sum=nums[start];
        }
        else {          //if this is the leaf node
            int mid=start+(end-start)/2;

            tree.left=makeATree(nums,start,mid);
            tree.right=makeATree(nums,mid+1,end);
            tree.sum=tree.left.sum+tree.right.sum;
        }
        return tree;
    }

    void update(int i, int val) {
       myUp(i,val,root);
    }
    private void myUp(int i,int val,Node tree){
        if(tree.start==tree.end){
            tree.sum=val;
        }
        else{
            int mid=tree.start+(tree.end-tree.start)/2;
            if(i<=mid){
                myUp(i,val,tree.left);
            }else {
                myUp(i,val,tree.right);
            }
            tree.sum=tree.left.sum+tree.right.sum;
        }
    }


    public int sumRange(int i, int j) {
       return calRange(i,j,root);

    }
    private int calRange(int start,int end,Node tree){
       if(start==tree.start&&end==tree.end){//edge case and leaf node case
           return tree.sum;
       }else{                               //if not the leaf node
           int mid =tree.start+(tree.end-tree.start)/2;//    tree.start tree.end ,          ，   start end        。
           if(end<=mid){                    //in total left
               return calRange(start,end,tree.left);//   
           }else if(start>=mid+1){   //   ，    mid+1 //in total right
               return calRange(start,end,tree.right);
           }else{                           //in part of the node range involve mid
               return calRange(start,mid,tree.left)+calRange(mid+1,end,tree.right);
           }
       }
    }
}

총결산
새로운 데이터 구 조 를 도입 하 는 것 은 적응 되 지 않 을 수 밖 에 없다. 흐리멍덩 한 데이터 구조의 개념 을 가지 고 인 코딩 을 하면 오류 가 발생 할 수 있다. 종이 로 약 도 를 그 려 내부 의 운영 체 제 를 볼 수 있다.