何为BIT BIT是一种数据结构，名为树其实用数组即可表达。其主要作用是给定了一个数组(或多维数组)，BIT可用来： O(logN)的复杂度计算给定范围的和,也就是求sum(low, high) O(logN)的复杂度更新数组的一个元素 其构造方法巧妙但简单，可谓大道至简。 给定一个数组a[0 ... N-1],长度N。 BIT表示为indexes[0 ... N],长度N+1。indexes[i]=sum(g(i) ... i], g(i)=i-i&(-i)，注意是左开右闭区间。i&(-i)得到的是一个数字的二进制表示中只留下最右的1后的数字，比如12=[1100],则12&(-12)只留下最右的1就成了4=[0100]。 注意到indexes[]从1开始计数，所以始终有indexes[0]=0。为了说明方便，在数组a[]前面添加了个元素0。 看图说话，如此构造后，原数组的和sum[0 ... i]就可以通过把能覆盖range[0 ... i]的indexes[]加起来得到。比如求sum[0 ... 14]，步骤如下，辅以图示。 先加上indexes[14]，覆盖了a[14], a[13]。 14=[1110],最右1留下后是2=[10],减去后得到12,加上indexes[12]。 12=[1100],最右1留下后是4=[100],减去后得到8,加上indexes[8]。 8=[1000],最右1留下后是8=[1000],减去后得到0，结束。 所以何为BIT,其本质是通过原数组构造一个新数组indexes[]，其中每个元素表示原数组中一段连续子数组的和。范围求和就从线性遍历原数组(O(N))，变成了在indexes[]中快速查找(O(logN))能覆盖所求范围的那几个元素。 而更新则是与求和相反的一个过程,原数组一个元素a[i]更新后，首先需要更新indexes[i]，然后要不停向上，更新每个覆盖了a[i]的indexes元素。比如,a[9]=2 -> a[9]=10,则有： 计算一个更新delta, delta=10-2，更新indexes[9]+=delta, 9=[1001],最右1留下后是1=[0001],加上后得到10,更新indexes[10] += delta。 10=[1010],最右1留下后是2=[0010],加上后得到12,更新indexes[12] += delta。 12=[1100],最右1留下后是4=[0100],加上后得到16,更新indexes[16] += delta。 代码如下: class BIT { private int[] indexes; private int[] nums; public BIT(int[] nums) { this.nums = nums; indexes = new int[nums.length + 1]; for (int i = 0; i < nums....

归并排序基于分治思想，基本步骤是把数组一分为二，分别排序，然后将两个排序好的数组合并，合并两个排序好的数组可以在O(N)的复杂度完成。根据T(N) = 2T(2/N) + N,可以推导出时间复杂度为O(NlogN)。代码如下： public void sort(int[] nums) { mergeSort(nums, 0, nums.length - 1); } private void mergeSort(int[] nums, int start, int end) { if (start >= end) { return; } int mid = start + (end - start) / 2; // Step 1: sort nums[start ... mid]. mergeSort(nums, start, mid); // Step 2: sort nums[mid+1 ... end]. mergeSort(nums, mid + 1, end); // Step 3: merge two sorted sub-arrays....

What’s Union Find? Union Find is useful in finding connected components. The idea behind UF is quite simple. You have N items initially. Each item forms its own group by setting parent to pointing to itself, i.e., parents[i] = i. Then you can union two items if they are connected or share some common properties in your problem definition. E.g., union(1,3) will connect item 1 and 3 and make their parents both pointing to the same item....

此一年波谲云诡，世事多艰，终于今宵。纵困苦艰难，江河依旧辽阔。新年至，昂首向前，爆竹声中，品人间烟火。 庚子弥年多诡谲，今岁今日终今宵。 寒随一夜冬雪去，暖入春风催竹梢。 稚齿犹恋除夕夜，三更欲等雄鸡叫。 家别万里相思浓，一柱清香扫尘嚣。

书接前文，pm升到partner level后，打算再接再厉，把clubhouse推向全宇宙。 之前一个房间参考微信设置只能容纳500人，pm说500人太少了，应该能容纳5亿人。 dev一时间不知如何回应，只能拉出了张小龙：做产品不是要节制么。 pm：做产品没有一成不变的方法论，每个产品我们都要追问自己几个问题：你这个产品的底层逻辑是什么？顶层设计在哪？最终交付价值是什么？过程的抓手在哪？如何保证闭环？你比别人的亮点在哪优势在哪？你的思考和沉淀又是什么？你的独特价值在哪？(*) dev：独特价值在哪？ pm：我们能容纳5亿人在一个房间，地球村我都嫌路远，我称之为地球房。 dev：可是我的技术能力可能实现不了这么高难度的服务，认真再想了下，以我的技术能力还是去掉可能二字。 pm：好，那就5000人吧，我已经让步了5个数量级了，可不能再讨价划价了哦。另外，考虑到你的技术能力，给你10%的冗余范围，就是你分布式环境下计数不用做到丝毫无误，高并发下从4500一下跳到5500再阻止人加入也可以，4500时就阻止人加入也可以。 dev：你是不是一开始就只想要5000人的房间。 pm：你知道你为什么还是Senior SDE么？ dev：请指教 pm：这个功能deliver时，我跟你1：1 请问，如何完成这个功能，限制房间人数为5000人，超过5000人时自动阻止其余人加入。 *注: 此段子转自fenng