123_123_123_123's blog

data structure
By 123_123_123_123, history, 6 years ago, In English

You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x1 y1 z1 x2 y2 z2 W updates the value of each block whose x coordinate is between x1 and x2 (inclusive), y coordinate between y1 and y2 (inclusive) and z coordinate between z1 and z2 (inclusive) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coordinate between y1 and y2 (inclusive) and z coordinate between z1 and z2 (inclusive). where n<=100,m<=1000 what will be the solution of this problem? I have a solution which has a complexity of n*m*log4(n*n) but I really doubt about log4(n*m) part. I am really confused.

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For 3D segtree solution Update and query is log^3(N).

Oh wait, N and M are small?

Make one segment tree. Then brute force other two dimensions with for loops.

→ Reply