Coders Packet

Dynamic Range Sum Queries in C++

By RANJITH RAMAMURTHY TEVNAN

  • code.cpp
  • a.exe
  • 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 Complete Code

    Comments

    No comments yet