奇怪的一道题

利用segment tree的思路，在插入节点时更新每个node的sum的值。

1.     class Node {
   
2.         public Node left;
   
3.         public Node right;
   
4.         public int start;
   
5.         public int end;
   
6.         public int sum;
   
7.         public Node(int start, int end) {
   
8.             this.start = start;
   
9.             this.end = end;
   
10.             this.sum = 0;
    
11.         }
    
12.     }
    
13.    
    
14.     private Node root;
    
15.     public Solution(int[] nums) {
    
16.         root = buildTree(nums,0,nums.length-1);
    
17.     }
    
18.    
    
19.     private Node buildTree(int[] nums, int start, int end) {
    
20.         if (start > end) return null;
    
21.         Node node = new Node(start, end);
    
22.         if (start == end) {
    
23.             node.sum = nums[start];
    
24.         } else {
    
25.             int mid = (start + end) >> 1;
    
26.             node.left = buildTree(nums, start, mid);
    
27.             node.right = buildTree(nums, mid+1, end);
    
28.             node.sum = node.left.sum + node.right.sum;
    
29.         }
    
30.         return node;
    
31.     }
    
32.    
    
33.     public void update(int i, int val) {
    
34.         update(root,i,val);
    
35.     }
    
36.    
    
37.     private void update(Node root, int i, int val) {
    
38.         if (root.start == i && root.end == i) {
    
39.             root.sum = val;
    
40.             return;
    
41.         }
    
42.         int mid = (root.start + root.end) / 2;
    
43.         if (i<=mid) {
    
44.             update(root.left, i, val);
    
45.         } else {
    
46.             update(root.right, i, val);
    
47.         }
    
48.         root.sum = root.left.sum+root.right.sum;
    
49.     }
    
50.    
    
51.     private int sumRange(Node root, int left, int right) {
    
52.         if (left>right || root == null) return 0;
    
53.         if (root.start==left && root.end==right) return root.sum;
    
54.         int mid = (root.start+root.end)>>1;
    
55.         return sumRange(root.left,left,mid)+sumRange(root.right,mid+1,right);
    
56.     }
    
57.    
    
58.     public int sumRange(int i, int j) {
    
59.         return sumRange(root,i,j);
    
60.     }

复制代码

这题问的是给一个range，求BST在range之间所有node的合吧？

madrid 发表于 2021-9-6 17:51
利用segment tree的思路，在插入节点时更新每个node的sum的值。

这题目是求值在 [min, max]间的和而不是矩阵系数在[min,max]的和，segment tree方向是不是搞错了？