Solution to hackerrank's list_max problem. The algorithm runs in O(m log n) but it's too slow due to being written in python.

list_max.py

"""The problem statement is the following:

You are given a list of size N, initialized with zeroes. You have to perform M operations on the list and output the maximum of final values of all the N elements in the list. For every operation, you are given three integers a, b and k. The value k needs to be added to all the elements ranging from index a through b (both inclusive).

Input Format

The first line will contain two integers N and M separated by a single space.
The next M lines will each contain three integers a, b and k separated spaces.
The numbers in the list are numbered from 1 to N.

Output Format

A single integer on a separate line line containing maximum value in the updated list.

Constraints

3 ≤ N ≤ 10^7
1 ≤ M ≤ 2 * 10^5
1 ≤ a ≤ b ≤ N
0 ≤ k ≤ 10^9
Sample input:

5 3
1 2 100
2 5 100
3 4 100
Sample output:

200
Explanation

After first update list will be 100 100 0 0 0.

After second update list will be 100 200 100 100 100.

After third update list will be 100 200 200 200 100.

So the required answer will be 200.
"""

# The solution is based on Petr Mitrichev's range extension of fenwick arrays -> http://petr-mitrichev.blogspot.com/2013/05/fenwick-tree-range-updates.html

def create(n):
    size = 1
    while n >= size:
        size *= 2
    return [0] * size


def range_add(fwam, fwaa, low, high, val):
    _update(fwam, fwaa, low, val, -val * (low - 1))
    _update(fwam, fwaa, high, -val, val * high)
    

def _update(fwam, fwaa, at, m, a):
    s = len(fwam)
    while at < s:
        fwam[at] += m
        fwaa[at] += a
        at += at & (-at)


def range_query(fwam, fwaa, at):
    m, a, st = 0, 0, at
    while at > 0:
        m += fwam[at]
        a += fwaa[at]
        at -= at & (-at)

    return m * st + a


def solve(n, operations):
    fwam, fwaa = create(n), create(n)
    for a, b, k in operations:
        range_add(fwam, fwaa, a, b, k)

    best, prev = 0, 0
    for i in xrange(1, n + 1):
        curr = range_query(fwam, fwaa, i)
        best = max(best, curr - prev)
        prev = curr

    return best


if __name__ == "__main__":
    n, m = map(int, raw_input().strip().split())
    operations = []
    for _ in xrange(m):
        operations.append(map(int, raw_input().strip().split()))
    print solve(n, operations)

# Takes ~10s to execute when n = 10 ** 7 and m = 2 * 10 ** 5 so a rewrite in a different language is necessary for acceptance as usual

I rewrote this stuff in C but it still got only 4/14 test cases :(