Static Range Sum Query

For (significantly) easy computation and shorter code, the library below is for 1-indexed sum queries.

You should convert your code to 1-indexed (in input) before using the library code.

1D Static Range Sum Query

Do note that the below code is 1-indexed. (The original array must be 1-indexed too) rsq(x, y) is inclusive of x and y.

The code stores the sum in sum. Please declare it to be long long if sum of the initial array will overflow integer.


  
  
2D Static Range Sum Query

  
Do note that the below code is 1-indexed. (The original array must be 1-indexed too) rsq(x1, y1, x2, y2) is inclusive of (x1, y1) and (x2, y2).

  
The code stores the sum in sum. Please declare it to be long long if sum of the initial array will overflow integer.

  


  
3D Static Range Sum Query

  
Do note that the below code is 1-indexed. (The original array must be 1-indexed too) rsq(x1, y1, z1, x2, y2, z2) is inclusive of (x1, y1, z1) and (x2, y2, z2).

  
The code stores the sum in sum. Please declare it to be long long if sum of the initial array will overflow integer.

  







  
Max Sum

  
  
1D Max Sum

  
Original array is arr and answer is stored at ans. The below algorithm will still give the correct answer when the numbers in the array are negative.

  

  
  
2D Max Sum

  
The below code is from Hubert's NOI Reference.

  
Array m[i][j] stores value in cell (i, j).

  
Array sum[i][j] stores sum of cells in the rectangle, whose top-left point is (0, 0) and bottom-right point (i, j).

  
Array dp[r1][c1][r2][c2] stores sum of cells in the rectangle, whose top-left point is (r1, c1) and bottom-right point (r2, c2).

  
Maximum score can be found in integer mx.

  
O(n^3) runtime can also be achieved by performing the 1D maxsum on the columns of all O(n^2) consecutive set of rows.

  








  
Longest Increasing Subsequence

  
The below code assumes that they are strictly increasing. To calculate longest decreasing subsequence, reverse the array then run the below codes.

  
N2 LIS

  
Original array is a and answer is stored at ans.

  
dp[x] stores the length of the LIS that ends with a[x]

  

  
N log N LIS

  
Original array is a and answer is stored at l. The array h is for speed up purposes.

  

 






  
Coin Change Ways

  
  
Bottom Up

  
V is the value to express in coins.

  
C is the number of coins and coin[i] stores the value of the ith coin (0 ≤ i < C)

  
This solution does not count repeated number of ways: Eg. 1+1+5 is considered the same way as 1+5+1. However, the code assumes that the coin values are unique (no repeated values)

  
Answer is found at dp[V]

  

  
  
  
Top Down

  
V is the value to express in coins.

  
C is the number of coins and coin[i] stores the value of the ith coin (0 ≤ i < C)

  
This solution does not count repeated number of ways: Eg. 1+1+5 is considered the same way as 1+5+1. However, the code assumes that the coin values are unique (no repeated values)

  
Answer is found by calling r(V, C-1)

  

  






  
Coin Change Minimum

  
  
Bottom Up

  
V is the value to express in coins.

  
C is the number of coins and coin[i] stores the value of the ith coin (0 ≤ i < C)

  
This code assumes that you can repeatedly use the same coin and a value of "-1" means there is no way to express that value in the given set of coins. (Although this method may be longer, it has less chance of WA due to low values of 'infinity')

  
Answer is found at dp[V]

  

  
  
  
Top Down

  
V is the value to express in coins.

  
C is the number of coins and coin[i] stores the value of the ith coin (0 ≤ i < C)

  
This solution does not count repeated number of ways: Eg. 1+1+5 is considered the same way as 1+5+1. However, the code assumes that the coin values are unique (no repeated values)

  
Answer is found by calling r(V, C-1)

  

  






  
Knapsack

  
  
Bottom Up

  
M is the maximum total size of items the bag can hold.

  
N is the number of items and v[i] stores the value of the ith item and s[i] stores the size of the ith item (0 ≤ i < N)

  
Answer is found at ans

  

  
  
  
Top Down

  
M is the maximum total size of items the bag can hold.

  
N is the number of items and v[i] stores the value of the ith item and s[i] stores the size of the ith item (0 ≤ i < N)

  
Answer is found by calling r(M, N-1)

  







  
Longest Common Subsequence

  
  
Bottom Up

  
a and b are the 2 strings (char array) and lena and lenb are their corresponding lengths.

  
Answer is found in dp[lena][lenb]

  

  
  
  
Top Down

  
a and b are the 2 strings (char array).

  
Answer is found by calling lcs(strlen(a), strlen(b))

  







  
Cutting Sticks

  
  
N3 Cutting Sticks

  
Original array is a and answer is stored at dp[0][N-1].

  

  
N2 Cutting Sticks

  
Original array is a and answer is stored at dp[0][N-1]. Code utilizes Knuth Yao algorithm for DP speedup.