Find the max number in list after m operations between indices a and b
For the record, don't ask us to write code for you. Writing the code is your responsibility; we will just critique it.


Why are you concerned about how long it takes to process each operation? The only thing that matters is the overall time and space requirement, and it's not a given that the best solution is going to operate by processing each operation in sequence. Thus, the timing does not belong in the loop. And I would even make the case that the timing does not belong in the run_testsn() functions. The timing belongs in your main function, which will call each of the run_testsn() in sequence. Each function should have one purpose only. It shouldn't be "Do this in this particular way and then time subunits of it.".
You've got a lot of unnecessary #includes. That just clutters up the code. Only use the ones you need.
Kudos to you for qualifying your C++ types with std::. But as @Morwenn said, don't forget to do it for functions from the C standard library too.
Is it necessary to take your input as a vector of vectors? It would make a lot more sense to build a struct with members int a; int b; int k; and then pass vectors of that around.
A map is pretty good for representing a sparse array; there are several other libraries out there that do better. See https://stackoverflow.com/questions/4306/what-is-the-best-way-to-create-a-sparse-array-in-c and https://stackoverflow.com/questions/21310680/sparse-array-in-c
You have two (soon-to-be three) functions that take the same parameter list and do the same thing. This looks like a job for an abstract base class (specifying the interface/params) and three subclasses of that class that each have implementations.
In run_tests2 you have


       std::pair&lt;std::map&lt;int, int&gt;::iterator, bool&gt; status =
         LIST.insert(std::make_pair(i, 0));

       status.first-&gt;second += k;



What's wrong with LIST[i] += k;? If the item doesn't exist yet, it will be auto-created with the default value (0). (And even if not, please declare it using auto status = as that type is just plain ugly and doesn't add anything. You're using C++11, take advantage of ways it can produce better code)