The numerical value of the number of figures thought of by the real-time update of the ranking list

Regular implementation of leaderboard
1. stand-alone ： Use normal values to store the scores of each user , The time complexity of updating a user's score is O(1), The time complexity of querying the ranking list of user scores is O(NlogN), If there is a total of 100000 Users , Yes 1000 Users are updating at the same time , So the time complexity is O(1000) + 1000 * O(100000 * log100000) = 1800000100=1800w operations
2. Distributed ： Distribution is generally based on redis Of zset Ordered set implementation , The score of each user is the score of each ordered set element score Value ,redis Of zset The underlying data structure of a set is a jump table , The time complexity of updating scores is O(logN), So use the skip table structure to realize the leaderboard ,10w Users also have 1000 When the user updates , The time complexity is just (1000 * log100000) = 180000=18w operations .

thus it can be seen , If it is stand-alone or distributed, the function of updating the ranking list in real time should be realized , Use ordered arrays ( For example, an ordered array based on the skip table structure ) It can meet the requirements , The time complexity is zero O(logN), Is there another structure that can meet the requirements , And the spatial complexity is only O(N) Well , The answer is yes.

1. The tree value is first an array structure , The elements in the array may store the prefixes and , It is also possible to store only its own element values , As for the serial number x The value stored in the element of is the prefix of the previous number of elements and by lowbit(x) The function determines ,lowbit(x) = x & （-x） That is to say x The binary of is 1 The lowest digit of , such as lowbit(6) = lowbit(110) = 2, lowbit(3)=lowbit(011)=1 etc.
2. For update operations , Such as update x Fractional value of serial number position , He's not just updating x The element value of position , He will also update those that contain x The value of the sequence number after the prefix value , Suppose there are 16 Array elements , Now you want to update the index location to 6 The element value of , In addition to updates 5 Outside the element value of this position , And update 0b110 + lowbit(110) = 0b1000=8 The value of this position , In addition, continue to update 0b1000+lowbit(0b1000) = 0x10000=16 The value of this position ( However, the value of this position is greater than the maximum array length , No need to update ), It is equivalent to adding lowbit The value of updates the element value of the corresponding index backwards
3. For the operation of getting prefix and or interval sum , Because the element value of the current sequence number may not include the element value of all the elements in front of it , So you need to add the previous value , For example, you need to get all the way to the index =6 And , Need to add an index 6 The element value of , Plus 0b110 - lowbit(0b110) = 0b100 The element value of the index , We need to continue to add 0b100-lowbit(0b100) = 0 The element value of the index , This is the complete prefix and
   For tree arrays , The time complexity of updating and finding any interval and operation is O(logN), The performance is quite ideal , The scene of ranking can also be transformed into tree array , However, the meaning of storage should be changed as follows , The fraction stored in the array is equal to the number of users of an index value , At this time, when I change my score, such as from oldScore Turned into newScore, Equivalent to index oldScore The number of users minus 1, Follow the previous update process , Then the index is newScore Number of users plus 1, Also follow the previous update process , Finally, I calculate from the index oldScore To newScore And , The sum of this range is the value of the change in the ranking of this user