Can anybody help me understand the solution of this problem using segment tree?

# | User | Rating |
---|---|---|

1 | Benq | 3601 |

2 | jiangly | 3598 |

3 | orzdevinwang | 3561 |

4 | ecnerwala | 3542 |

5 | cnnfls_csy | 3539 |

6 | Radewoosh | 3532 |

7 | inaFSTream | 3478 |

8 | maroonrk | 3451 |

9 | tourist | 3434 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 165 |

3 | awoo | 161 |

3 | TheScrasse | 161 |

5 | nor | 160 |

6 | maroonrk | 158 |

7 | SecondThread | 155 |

8 | Um_nik | 150 |

9 | Geothermal | 145 |

9 | BledDest | 145 |

Can anybody help me understand the solution of this problem using segment tree?

I have been learning 2-D BIT lately.

But I am having difficulty implementing range updates in it.

Eg. Suppose we have a matrix M[][].There are 2 types of queries:

1.ADD x1 y1 x2 y2 val

This adds val to all matrix elements which have their x-coordinate between x1 and x2 and y-coordinate between y1 and y2.

2.SUM x1 y1 x2 y2

This query returns the sum of all matrix elements which have their x-coordinate between x1 and x2 and y-coordinate between y1 and y2.

I am having trouble implementing the first query using 2-D BIT.

Had point(x1, y1) and point(x2, y2) been same, following code would work :

void update(int x1, int y1, ll val)

{

```
int x, y;
x=x1;
while(x<=n){
y=y1;
while(y<=m){ //Update y coordinate
ft[x][y]+=val; //ft stores BIT
y+=(y&-y);
}
x+=(x&-x);
}
return;
```

}

How to go about it if I have to update the whole range?

So, I was trying to solve this problem on a codechef contest that ended just now.I tried to reduce the expression of g(n).The maximum I could simplify is upto this point:

g(n) = pow(4, n) + 2*(pow(4,n)-1)/3 + Summation of (pow(4,n-k)*f(k)) where k ranges from n to 1.

But I couldn't find a way to find sum of function f upto a point.

On looking at accepted codes, I find that this question was to be done using Matrix Multiplication, kind of what we do in finding fibonacci numbers.

I want to know how do you guess the values in the matrix to be multiplied.?Is there a particular way to be followed around such questions..?

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/04/2024 18:40:31 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|