1
\$\begingroup\$

https://leetcode.com/problems/range-sum-query-mutable/

I am trying to solve this question using dynamic programming.

I guess the guys in leetcode want to limit us to use segment tree or one of the other solutions.

using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;

namespace DynamicProgrammingQuestions
{

        /// <summary>
        ///https://leetcode.com/problems/range-sum-query-mutable/
        /// ["NumArray", "sumRange","sumRange","sumRange","update","update","update","sumRange","update","sumRange","update"]
        ///[[[0,9,5,7,3]],[4,4],     [2,4],     [3,3]     ,[4,5],   [1,7]   ,[0,8]    ,[1,2],[1,9],[4,4],[3,4]]
        /// [   null,       3,        15,        7,         null    ,null    ,null      ,12,null,5,null]
        /// </summary>
        [TestClass]
        public class UnitTest1
        {
            [TestMethod]
            public void TestMethod1()
            {
                int[] nums = {0, 9, 5, 7, 3};
                NumArray numArray = new NumArray(nums);
                Assert.AreEqual(3, numArray.SumRange(4, 4));
                Assert.AreEqual(15, numArray.SumRange(2, 4));
                Assert.AreEqual(7, numArray.SumRange(3, 3));
                numArray.Update(4,5);
                numArray.Update(1,7);
                numArray.Update(0,8);
                // 8,7,5,7,5
                Assert.AreEqual(12, numArray.SumRange(1, 2));
            }
        }
    
        public class NumArray
        {
            int[] _dp;
            int[] _nums;
            public NumArray(int[] nums)
            {
                _dp = new int[nums.Length + 1];
                //0,1,2,3
                //  1,4,9 
                for (int i = 0; i < nums.Length; i++)
                {
                    _dp[i + 1] = _dp[i] + nums[i];
                }
                _nums = nums;
            }
    
            public void Update(int index, int val)
            {
                int old = _nums[index];
                _nums[index] = val;
                for (int i = index; i < _dp.Length - 1; i++)
                {
                    _dp[i + 1] = _dp[i + 1] - old + val;
                }
    
            }
    
            public int SumRange(int left, int right)
            {
                return _dp[right + 1] - _dp[left];
            }
        }      
  

}

here is my code. i'm trying to understand if I can optimize it? can you please suggest runtime performance optimizations?

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.