奇怪的一道题

您好！
本帖隐藏的内容需要积分高于 168 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 168 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

抛砖引玉。。看了一下说只需要实现query，也就是说我们可以假定data structure是个BST。然后这道题就是一个包装了一层的LC原题：给定一个BST，求两个数之间所有node的和

利用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.     }

复制代码

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

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

segment tree
BIT


对不起
上面不对. 读错了.
是个stream....BST?

没理解错的话，用hashmap记录每个value的idx，再用prefix sum就行了吧....

理解错了... 应该是用BIT，存不大于k的所有数之和，可以算出任意区间的和

能展开说下这道题目如何解吗？

stream range sum。。 在刷题网有原题的。。三菱三和散灵气，segment tree

楼上理解错了吧，楼主说的是Range between [low, high], 你给的题号是index between [low, high]

WooMeow 发表于 2021-8-31 11:47
抛砖引玉。。看了一下说只需要实现query，也就是说我们可以假定data structure是个BST。然后这道题就是一个 ...

请问题号是多少？

WooMeow 发表于 2021-8-31 09:47
抛砖引玉。。看了一下说只需要实现query，也就是说我们可以假定data structure是个BST。然后这道题就是一个 ...

LC 938? 可是O(N)的时间复杂度感觉完全没有优化啊

我觉得题意是只关心query 的时间复杂度，应该还是用hashmap最高效。