fork download
copy 
  1. class FTree:
  2.     def __init__(self, f):
  3.         self.n = len(f)
  4.         self.ft = [0] * (self.n + 1)
  5.  
  6.         for i in range(1, self.n + 1):
  7.             self.ft[i] += f[i - 1]
  8.             if i + self.lsone(i) <= self.n:
  9.                 self.ft[i + self.lsone(i)] += self.ft[i]
  10.  
  11.     def lsone(self, s):
  12.         return s & (-s)
  13.  
  14.     def query(self, i, j):
  15.         if i > 1:
  16.             return self.query(1, j) - self.query(1, i - 1)
  17.  
  18.         s = 0
  19.         while j > 0:
  20.             s += self.ft[j]
  21.             j -= self.lsone(j)
  22.  
  23.         return s
  24.  
  25.     def update(self, i, v):
  26.         while i <= self.n:
  27.             self.ft[i] += v
  28.             i += self.lsone(i)
  29.  
  30.     def select(self, k):
  31.         p = 1
  32.         while (p * 2) <= self.n: p *= 2
  33.  
  34.         i = 0
  35.         while p > 0:
  36.             if i + p < len(self.ft) and k > self.ft[i + p]:
  37.                 k -= self.ft[i + p]
  38.                 i += p
  39.             p //= 2
  40.  
  41.         return i + 1
  42.  
  43. def main():
  44. 	for size in range(1,1000+1):
  45. 		ft = FTree([1]*size)
  46. 		for i in range(1,size+1):
  47. 			if ft.select(i)!=i:
  48. 				print(f'Failed at size {size} at index {i}')
  49. 				exit(1)
  50.  
  51. main()
  52.  
  53.  
Success #stdin #stdout 1.98s 9140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YpJSdE
language:
Python 3 (python  3.12)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!