forked from SylvanHuang/RecSys
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtool.py
More file actions
38 lines (32 loc) · 893 Bytes
/
tool.py
File metadata and controls
38 lines (32 loc) · 893 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# -*- coding: utf-8 -*-
class FenwickTree(object):
def __init__(self, length):
self.n = length
self.bit = [0] * (self.n + 1)
@classmethod
def lowbit(cls, num):
return num & -num
def add(self, index, value):
while index <= self.n:
self.bit[index] += value
index += self.lowbit(index)
def get(self, index):
ret = 0
while index > 0:
ret += self.bit[index]
index -= self.lowbit(index)
return ret
def find_kth(self, k):
ret = 0
cnt = 0
index = 1
while index <= self.n:
index <<= 1
while index > 0:
ret += index
if ret >= self.n or cnt + self.bit[ret] >= k:
ret -= index
else:
cnt += self.bit[ret]
index >>= 1
return ret + 1