Coders Packet

Dynamic Range Sum Queries in C++

By RANJITH RAMAMURTHY TEVNAN

Given an array of n integers, and given q queries, 1. update the value at position k to u 2. what is the sum of values in the range [a,b]?

This is a project involving Dynamic Range Sum Queries in C++. This code allows us to find the sum of values in a range and also updating individual values in different queries.

In this, an array of length n is given as an input initially. Then, queries are asked which could either be the sum of values in a range or updating a certain value in the array.

Finding the sum of the range or updating a value in the array only takes O(logn) time. It works using a data structure called a segment tree.

In the queries, if 1 is chosen, then we can update a value at a certain position by giving the position and the value to be put there. For eg - 3 8 will update the value at position 3 to 8.

If 2 is chosen, then we can find the sum of values in that range. For eg - 2 5 will give the sum of elements at positions 2,3,4 and 5.

The zip file contains the C++ code as well as a.exe executable file.

 

Download project

Reviews Report

Submitted by RANJITH RAMAMURTHY TEVNAN (ranjith1604)

Download packets of source code on Coders Packet