MrPoJ's blog

By MrPoJ, history, 15 months ago, In English,

Hello CodeForces Community!

I decided to share every single method i know about Sum query from simple to hard!

so let's start.

1-simple Sum query without any update :

given an array of integers and queries ask you about sum of a range.

prefix_sum O(N + Q)
SparsTable O(Nlog(N))

2-Sum query with index update :

having 2 type of queries one ask about sum in range and one add a value to index i.

Segment_tree O(Nlog(N))
Segment Tree II O(NLog(N))
Binary Indexed Tree (Fenwick tree) O(NLog(N))
Sqrt Decomposition O(Nsqrt(N))

3-Sum query with range update:

2 type of queries one add value in range [L, R] and one sum of range.

Segment Tree (lazy) O(NLog(N))
Sqrt Decomposition O(Nsqrt(N))

If anyone have code of range update for sqrt decomposition i'll be thankful :)

and if anyone have other method or better code i'll be thankful again if he/she share with us :)

i'll add problems soon

In the bleak midwinter...

Read more »

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

By MrPoJ, history, 16 months ago, In English,

Hello there .

i'm searching for good tutorial for K.M.P. algorithm but as you know it's not a simple one and i can't understand the tutorials in web ( geeksforgeeks and topcoder ) .

so i'm asking if you have any good one share it :) and also if you have good problems about it i will be thankful .

Read more »

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