title: Sum of 2d array subsection in Python
body: <p>Here is a task description:
  I have 2d array NxM, N, M&lt;1000, and there are K(K&lt;100000) sets of coordinates(x1, x2, y1, y2). I need to sum all the elements in rectangle(x1, x2, y1, y2).<br>
  My code works but I need make it faster cause the largest tests dont work in required time. </p>
  
  <p>Here it is: </p>
  
  <pre><code>def build_y(cx, fx, lx, cy, fy, ly):
      if fy == ly:
          if fx == lx:
              t[cx][cy] = a[fx][fy]
          else:
              t[cx][cy] = t[cx*2][cy] + t[cx*2+1][cy];
      else:
          my = int((fy + ly) / 2)
          build_y (cx, fx, lx, cy*2, fy, my)
          build_y (cx, fx, lx, cy*2+1, my+1, ly)
          t[cx][cy] = t[cx][cy*2] + t[cx][cy*2+1]
  
  def build_x(cx, fx, lx):
      if fx != lx:
          mx = int((fx + lx) / 2)
          build_x (cx*2, fx, mx)
          build_x (cx*2+1, mx+1, lx)
      build_y (cx, fx, lx, 1, 0, m-1)
  
  def sum_y (cx, cy, tfy, tly, fy, ly):
      if fy &gt; ly:
          return 0
      if fy == tfy and tly == ly:
          return t[cx][cy]
      tmy = int((tfy + tly) / 2)
      return sum_y(cx, cy*2, tfy, tmy, fy, min(ly, tmy)) + sum_y(cx, cy*2+1, tmy+1, tly, max(fy, tmy+1), ly)
  def sum_x(cx, tfx, tlx, fx, lx, fy, ly):
      if fx &gt; lx:
          return 0
      if fx == tfx and tlx == lx:
          return sum_y(cx, 1, 0, m-1, fy, ly)
      tmx = int((tfx + tlx) / 2)
      return sum_x(cx*2, tfx, tmx, fx, min(lx, tmx), fy, ly) + sum_x(cx*2+1, tmx+1, tlx, max(fx, tmx+1), lx, fy, ly)
  fin = open('input.txt', 'r').read().split()
  n = int(fin[0])
  m = int(fin[1])
  k = int(fin[2])
  a = []
  b = []
  t = [0]*3*n
  for i in range(3*n):
      t[i] = [0]*3*m
  for i in range(n):
      a.append([int(j) for j in fin[3+i*m:3+i*m+m]])
  build_x(1, 0, n-1)
  for i in range(k):
      b.append([int(j) for j in fin [3+n*m+4*i:3+n*m+4*i+4]])
  for i in range(k):
      print(sum_x(1, 0, n-1, b[i][0]-1, b[i][2]-1, b[i][1]-1, b[i][3]-1))
  </code></pre>