algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

range-sum-query-immutable.cpp (450B)

      1 class NumArray {
      2 public:
      3     unordered_map<int, int> map {};
      4     NumArray(vector<int>& nums) {
      5         // init with nums list
      6         int prefix = 0;
      7         for(size_t i = 0; i < nums.size(); ++i) {
      8             map[i] = prefix;
      9             prefix += nums[i]; 
     10         }
     11         map[nums.size()] = prefix;
     12     }
     13     
     14     int sumRange(int left, int right) {
     15         // query: return sum[left:right]
     16         return map[right + 1] - map[left];
     17     }
     18 };