fork download
copy 
  1. class FenwickTree:
  2.     def __init__(self, size):
  3.         self.size = size
  4.         self.tree = [0] * (size + 1)
  5.  
  6.     def add(self, index, value):
  7.         while index <= self.size:
  8.             self.tree[index] += value
  9.             index += index & -index
  10.  
  11.     def sum(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_add(self, left, right, value):
  19.         self.add(left, value)
  20.         self.add(right + 1, -value)
  21.  
  22.     def range_sum(self, left, right):
  23.         return self.sum(right) - self.sum(left - 1)
  24.  
  25. import sys
  26.  
  27. def main():
  28.     input = sys.stdin.read
  29.     data = input().strip().split()
  30.  
  31.     index = 0
  32.     N = int(data[index])
  33.     Q = int(data[index + 1])
  34.     index += 2
  35.  
  36.     P = list(map(int, data[index:index + N]))
  37.     index += N
  38.  
  39.     # Create Fenwick Tree for handling updates and queries
  40.     fenwick = FenwickTree(N)
  41.  
  42.     result = []
  43.     for _ in range(Q):
  44.         T = int(data[index])
  45.         if T == 0:
  46.             l = int(data[index + 1])
  47.             r = int(data[index + 2])
  48.             c = int(data[index + 3])
  49.             fenwick.range_add(l, r, c)
  50.             index += 4
  51.         elif T == 1:
  52.             l = int(data[index + 1])
  53.             r = int(data[index + 2])
  54.             c = int(data[index + 3])
  55.             fenwick.range_add(P[l - 1], P[r - 1], c)  # use P to index
  56.             index += 4
  57.         elif T == 2:
  58.             l = int(data[index + 1])
  59.             r = int(data[index + 2])
  60.             result.append(fenwick.range_sum(l, r))
  61.             index += 3
  62.         elif T == 3:
  63.             l = int(data[index + 1])
  64.             r = int(data[index + 2])
  65.             result.append(fenwick.range_sum(P[l - 1], P[r - 1]))  # use P to index
  66.             index += 3
  67.  
  68.     # Print results for all queries of type 2 and 3
  69.     sys.stdout.write('\n'.join(map(str, result)) + '\n')
  70.  
  71. if __name__ == "__main__":
  72.     main()
Success #stdin #stdout 0.03s 9700KB
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/1awULF
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!