MohammadParsaElahimanesh's blog

need help in segment tree problem . . .
By MohammadParsaElahimanesh, history, 3 years ago, In English

Hello,

we have array A[n][n] and q queries. each time we get l r x means we should assign A[i][j] = x (l <= i,j <= r)

at end we want to know sum of elements in A, initially A[i][j] = 0

n <= 200'000

q <= 200'000

How we can solve this problem or what is the best time complexity we can reach?

thanks in advance

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 6   Vote: I like it +5 Vote: I do not like it

Edit: the problem is slightly different, so I don't think divide and conquer works.

UPD:

idea (I don't know if it works)
→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

You can do this in n^2, start from reverse,i.e., last query to first query , created horizonal and vertical jump pointer so that you can act like it's dp and never visit already colored
I guess parent pointer thing might get the complexity to $$$n^2 log^*n$$$ or $$$n^2 logn$$$, if we use path compression using dsu or might be some binary lifting kind of stuff.

For N log N , you can work construct how will final diagonal look like after all the queries , this you can do with same previous algorithm, with this you also have to store the query index which the diagonal cell is part of., And then iterate on diagonal cells and sum up the height accordingly depending upon what query it is part of.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not sure, but can we use 2-D segment trees with lazy updates? Each query will be answered in O(log2n).

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Generally, you can't use lazy propagation in 2D segment trees.

    → Reply