fork download
copy 
  1. class FenwickTree:
  2.     def __init__(self, size):
  3.         self.size = size
  4.         self.tree = [0] * (size + 1)
  5.  
  6.     def update(self, index, delta):
  7.         while index <= self.size:
  8.             self.tree[index] += delta
  9.             index += index & -index
  10.  
  11.     def query(self, index):
  12.         total = 0
  13.         while index > 0:
  14.             total += self.tree[index]
  15.             index -= index & -index
  16.         return total
  17.  
  18.     def range_update(self, left, right, delta):
  19.         self.update(left, delta)
  20.         self.update(right + 1, -delta)
  21.  
  22.     def range_query(self, left, right):
  23.         return self.query(right) - self.query(left - 1)
  24.  
  25. def process_queries(N, Q, permutation, queries):
  26.     fenwick = FenwickTree(N)
  27.     results = []
  28.  
  29.     for query in queries:
  30.         T = query[0]
  31.         if T == 0:  # Type 0 update
  32.             l, r, c = query[1], query[2], query[3]
  33.             fenwick.range_update(l, r, c)
  34.         elif T == 1:  # Type 1 update
  35.             l, r, c = query[1], query[2], query[3]
  36.             fenwick.range_update(permutation[l - 1], permutation[r - 1], c)
  37.         elif T == 2:  # Type 2 query
  38.             l, r = query[1], query[2]
  39.             result = fenwick.range_query(l, r)
  40.             results.append(result)
  41.         elif T == 3:  # Type 3 query
  42.             l, r = query[1], query[2]
  43.             result = fenwick.range_query(permutation[l - 1], permutation[r - 1])
  44.             results.append(result)
  45.  
  46.     return results
  47.  
  48. def main():
  49.     import sys
  50.     input = sys.stdin.read
  51.     data = input().strip().splitlines()
  52.  
  53.     first_line = data[0].split()
  54.     N = int(first_line[0])
  55.     Q = int(first_line[1])
  56.  
  57.     permutation = list(map(int, data[1].split()))
  58.     queries = []
  59.  
  60.     for i in range(2, 2 + Q):
  61.         queries.append(list(map(int, data[i].split())))
  62.  
  63.     results = process_queries(N, Q, permutation, queries)
  64.  
  65.     # Output results for type 2 and 3 queries
  66.     for result in results:
  67.         print(result)
  68.  
  69. if __name__ == "__main__":
  70.     main()
Success #stdin #stdout 0.03s 9800KB
comments (?)
stdin
copy 
5 6
3 1 5 4 2
0 2 4 2
1 2 4 3
2 3 4
0 2 5 1
3 2 4
3 1 3
stdout
copy 
0
6
-5
https://ideone.com/srRMUT
language:
Python 3 (python  3.9.5)
created:
5 days ago
visibility:
public

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!