Hi all,

Today I was working on this problem. I recognize that this is a data structure problem, but I am curious on how to solve it with:

- Segtree + lazy propagation and 2.Binary indexed tree

Thank you much in advance!

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

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3567 |

3 | tourist | 3520 |

4 | maroonrk | 3421 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3309 |

8 | Benq | 3283 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

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

1 | Errichto | 194 |

2 | antontrygubO_o | 192 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | Radewoosh | 167 |

6 | tourist | 166 |

7 | Um_nik | 165 |

8 | ko_osaga | 163 |

8 | McDic | 163 |

10 | Geothermal | 158 |

Hi all,

Today I was working on this problem. I recognize that this is a data structure problem, but I am curious on how to solve it with:

- Segtree + lazy propagation and 2.Binary indexed tree

Thank you much in advance!

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/06/2020 00:21:45 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Just make a segment tree such that each node contains the sum of squres of numbers in its range and the sum of the numbers. For the first update what we are doing for each range while updating in fact is: (a[l]+c)^2 + (a[l+1]+c)^2.....(a[r]+c)^2 so since (a+b)^2=a^2 + 2ab + b^2 Then the last sum is equal to : (sum of the squres of current numbers of the range)+(2*c*(sum of current numbers of the range))+((r-l+1)*(c^2)) Where c is the number that we are increasing the interval by. The second update query is easy. And of course sum query is easy since we could do the update.

Do you use lazy propagation?

Yes of course.I submitted my solution and got AC. Here is my code Code.