code_tycoon's blog

By code_tycoon, history, 3 years ago, In English

This question was asked in hackwithinfy, I could not approach this problem anyhow, can anyone tell me the optimal approach to solve these type of problems and the solution of this specific problem. Here is the question : part1 part2

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by code_tycoon (previous revision, new revision, compare).

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

Seems solvable with a simple segment tree.

Maintain sum of triplets, sum of pairs, and sum of elements in each node of a segment tree. Merging nodes should be pretty straightforward.