Basic Algorithm (2)

This video is on high precision, prefix sum, and difference.

High precision

  • A + B: Add two large integers
  • A - B: Subtracts two large integers
  • A × b: a large integer multiplied by a small integer
  • A present b: A large integer divided by a small integer

We don’t see much of A cross B and A ÷ B, we don’t talk about it in the course.

Storage of large integers: Use an array to store each bit of a large integer.

We’re going to store the ones bit of the big integer at the first place, and the highest bit of the big integer at the last place, so we’re going to use little endian order.

High precision addition

  • A + B

    Algorithm title: ACwing-791: High Precision addition

    The process of high-precision addition is to simulate the process of manual addition by adding each digit in turn and carrying the previous digit.

    // C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> add(vector<int> &a, vector<int> &b) {
    int c = 0; / / carry
    vector<int> res;
    for(int i = 0; i < a.size() || i < b.size(); i++) {
        if(i < a.size()) c += a[i];
        if(i < b.size()) c += b[i];
        res.push_back(c % 10);
        c /= 10;
    }
    // If the highest bit has a carry
    if(c) res.push_back(c);
    return res;
    
}

int main(a) {
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    vector<int> res = add(A, B);
    for(int i = res.size() - 1; i >= 0; i--) printf("%d", res[i]);
}
Copy the code
    // java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	private static List<Integer> add(List<Integer> num1, List<Integer> num2) {
		int c = 0; / / carry
		List<Integer> res = new ArrayList<>();
		for (int i = 0; i < num1.size() || i < num2.size(); i++) {
			if (i < num1.size()) c += num1.get(i);
			if (i < num2.size()) c += num2.get(i);
			res.add(c % 10);
			c /= 10;
		}
		// see if there is a carry
		if (c > 0) res.add(c);
		return res;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String n1, n2;
		n1 = reader.readLine();
		n2 = reader.readLine();
		List<Integer> num1 = new ArrayList<>(), num2 = new ArrayList<>();
		for (int i = n1.length() - 1; i >= 0; i--) num1.add(n1.charAt(i) - '0');
		for (int i = n2.length() - 1; i >= 0; i--) num2.add(n2.charAt(i) - '0');
		List<Integer> res = add(num1, num2);
		for (int i = res.size() - 1; i >= 0; i--) System.out.print(res.get(i)); }}Copy the code

High precision subtraction

  • A - B

    So let’s figure out what the relative sizes of A and B are

    • A >= B, then directly calculate the subtraction
    • A < BTo calculate theB - A, and prefix the result with a minus sign-

    The process of high-precision subtraction is also the process of manual subtraction. When a certain bit is not subtracted enough, there will be the concept of borrowing

    Algorithm title: ACwing-792: High-precision subtraction

    // C++
#include<iostream>
#include<vector>
#include<string>

using namespace std;
// Compare the size of A and B, return true if A >= B, false otherwise
bool cmp(vector<int> &A, vector<int> &B) {
    if(A.size() ! = B.size())return A.size() > B.size(); // The length of A is not equal to that of B
    else {
        for(int i = A.size() - 1; i >= 0; i--) {
            if(A[i] ! = B[i])return A[i] > B[i]; // When the length is equal, start with the highest bit. If only one bit is different, the size relationship can be found
        }
        return true; // A is equal to B}}vector<int> sub(vector<int> &A, vector<int> &B) {
    vector<int> C;
    // Use a variable t to represent the borrowing
    for(int i = 0, t = 0; i < A.size(); i++) {
        t = A[i] - t;   A[I] -b [I] -t = A[I] -b [I] -t
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10); // If the result is negative, then +10, then modulo 10, can cover both integer and negative results
        if(t < 0) t = 1; // When the original result is negative, we need to borrow t to 1
        else t = 0; // Otherwise, reset the borrowing t to 0
    }
    // remove the prefix 0. If the length is greater than 1 and the highest bit is 0, remove the highest bit
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main(a) {
    
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    
    if(cmp(A, B)) {
        vector<int> C = sub(A, B);
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    } else {
        vector<int> C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]); }}Copy the code
    // java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	public static List<Integer> sub(List<Integer> num1, List<Integer> num2) {
		List<Integer> res = new ArrayList<>();
		for (int i = 0, t = 0; i < num1.size(); i++) {
			t = num1.get(i) - t;
			if (i < num2.size()) t -= num2.get(i);
			res.add((t + 10) % 10);
			if (t < 0) t = 1;
			else t = 0;
		}
		// drop the prefix 0
		while (res.size() > 1 && res.get(res.size() - 1) = =0) res.remove(res.size() - 1);
		return res;
	}

	// return true if num1 >= num2, false otherwise
	public static boolean cmp(List<Integer> num1, List<Integer> num2) {
		if(num1.size() ! = num2.size())return num1.size() > num2.size();
		else {
			for (int i = num1.size() - 1; i >= 0 ; i--) {
				if(num1.get(i).intValue() ! = num2.get(i).intValue())return num1.get(i) > num2.get(i);
			}
			return true; // num1 == num2}}public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String n1, n2;
		n1 = reader.readLine();
		n2 = reader.readLine();
		List<Integer> num1 = new ArrayList<>(), num2 = new ArrayList<>();
		for (int i = n1.length() - 1; i >= 0; i--) num1.add(n1.charAt(i) - '0');
		for (int i = n2.length() - 1; i >= 0; i--) num2.add(n2.charAt(i) - '0');
		
		if (cmp(num1, num2)) {
			List<Integer> res = sub(num1, num2);
			for (int i = res.size() - 1; i >= 0 ; i--) System.out.print(res.get(i));
		} else {
			List<Integer> res = sub(num2, num1);
			System.out.print("-");
			for (int i = res.size() - 1; i >= 0; i--) System.out.print(res.get(i)); }}}Copy the code

High precision multiplication

  • A × b

    Look at B as A whole, multiply with every digit of A. For example, 123 x 12.

    First, start from the lowest point of A, calculate 3 × 12, get 36, then the ones place in the result is: 36% 10 = 6, resulting in 36/10 = 3 carry; Continuing with the next digit, 2 × 12 gives you 24, plus carry 3 gives you 27. The resulting tens place is 27%10 = 7, resulting in a carry of 27/10 = 2; Continuing to the next place, 1 × 12 + 2 = 14, the result in the hundreds place is 14%10 = 4, resulting in 14/10 = 1, the final result is 1476.

    Algorithm title: ACwing-793: High Precision Multiplication

    // C++
#include<iostream>
#include<vector>
#include<string>
using namespace std;

vector<int> multi(vector<int> &A, int b) {
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i++) {
        t += b * A[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if(t > 0) C.push_back(t);
    // drop the prefix 0
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main(a) {
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    
    vector<int> C = multi(A, b);
    
    for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
}
Copy the code
    // java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	
	public static List<Integer> multi(List<Integer> num1, int num2) {
		int t = 0;
		List<Integer> res = new ArrayList<>();
		for (int i = 0; i < num1.size(); i++) {
			t += num1.get(i) * num2;
			res.add(t % 10);
			t /= 10;
		}
		if (t > 0) res.add(t);
		while (res.size() > 1 && res.get(res.size() - 1) = =0) res.remove(res.size() - 1);
		return res;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String n1 = reader.readLine();
		int n2 = Integer.parseInt(reader.readLine());
		List<Integer> num1 = new ArrayList<>();
		for (int i = n1.length() - 1; i >= 0; i--) num1.add(n1.charAt(i) - '0');
		List<Integer> res = multi(num1, n2);
		for (int i = res.size() - 1; i >= 0; i--) System.out.print(res.get(i)); }}Copy the code

High precision division

  • A present b

    The process of the algorithm is to simulate the process of manual division. Divide from the highest place, quotient and mod. The remainder of each round, times 10, plus the next digit, is the dividend of the next round.

    Let’s say 123 ÷ 12

Algorithm title: ACwing-794: High precision Division

// C++
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

// return the remainder
vector<int> div(vector<int> &A, int b, int &r) {
    vector<int> C;
    r = 0; // The initial remainder is 0
    for(int i = A.size() - 1; i >= 0; i--) {
        // Divide from the highest digit
        r = r * 10 + A[i]; // The dividend of the round
        C.push_back(r / b); // Dividend divided by b quotient
        r = r % b; // Mod b
    }
    // If C is stored from high to low, invert vector
    reverse(C.begin(), C.end());
    // remove prefix 0
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main(a) {
    string a;
    int b;
    vector<int> A;
    cin >> a >> b;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    int r = 0;
    vector<int> C = div(A, b, r);
    for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    printf("\n%d\n", r);
}
Copy the code
// java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

	static class Pair {
		List<Integer> quotient;
		int remainder;

		public Pair(List<Integer> quotient, int remainder) {
			this.quotient = quotient;
			this.remainder = remainder; }}public static Pair div(List<Integer> num1, int num2) {
		List<Integer> quotient = new ArrayList<>();
		int r = 0;
		for (int i = num1.size() - 1; i >= 0 ; i--) {
			r = r * 10 + num1.get(i);
			quotient.add(r / num2);
			r = r % num2;
		}
		/ / reverse
		Collections.reverse(quotient);
		// remove prefix 0
		while (quotient.size() > 1 && quotient.get(quotient.size() - 1) = =0) quotient.remove(quotient.size() - 1);
		return new Pair(quotient, r);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String n1 = reader.readLine();
		int n2 = Integer.parseInt(reader.readLine());
		List<Integer> num1 = new ArrayList<>();
		for (int i = n1.length() - 1; i >= 0; i--) num1.add(n1.charAt(i) - '0');
		Pair res = div(num1, n2);
		for (int i = res.quotient.size() - 1; i >= 0 ; i--) System.out.print(res.quotient.get(i));
		System.out.printf("\n%d\n", res.remainder); }}Copy the code

The prefix and

One-dimensional prefix sum

Suppose you have an array: a 1, a 2, a 3, a 4, a 5,…… , a n (note that the subscript starts at 1)

Prefix and S I = a 1 + a 2 + a 3 +…. Plus a PI I.

In particular, we can define S 0 = 0, so that any interval [l, r] can be computed by the formula S r – S L -1 without any special treatment to the boundary (when l = 1, To find the sum of all the numbers [l, r] is to find S, r.

The best use of the prefix sum is to find the sum of all numbers in any interval. For example, the sum of all elements of the interval [l, r] is required. If there are no prefixes and arrays, we need to traverse the original array in order n time. With prefixes and arrays, we just need to compute S r minus S L minus 1, O(1). Because S r = a 1 + a 2 + a 3 +…. + a l-1 + a l + ….. + a r

S l-1 = a 1 + a 2 + a 3 +…. + a l-1

Practice: ACwing-795: prefix and

// C++
#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int s[N];

int main(a) {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        s[i] += s[i - 1]; // Input arrays and compute prefixes and put them together
    };
    while(m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}
Copy the code

Two-dimensional prefix sum

The array prefix sum above may be too simple. Here is an advanced version: matrix prefix sum (2d)

Let’s say I have the following matrix

A 11, a 12, a 13, a 14,……. , a 1 n

A 21, a 22, a 23, a 24,……. , a 2 n

.

.

A M1, a m2, a M3, a m4,….. , a mn

The prefix and S ij represent the sum of all the numbers at the point A, ij and its upper-left region.

After simple derivation (area calculation), it can be obtained that S ij = S I -1,j + S I, J-1 + a ij – S I -1,j-1

If the upper left boundary point is [x1, y1] and the lower right boundary point is [x2, y2], the sum of the submatrices between these two points (also the sum of all numbers in any interval) can be obtained by simple derivation

S = S x2, y2-s x1-1, y2-s x2,y1-1 + S x1-1,y1-1

Exercise: ACwing-796: Sum of submatrices

// C++
#include<iostream>
using namespace std;

const int N = 1010;
int a[N][N];
int n, m, q;

int main(a) {
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; // Enter and calculate prefix and at the same time}}while(q--) {
        int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1]);
    }
    
    return 0;
}
Copy the code

Summary: prefixes and ideas are used to quickly solve the sum of all numbers in any interval. Time complexity O(1)

The differential

Difference is the inverse of the prefix sum

A one-dimensional finite difference

Suppose I have an array, a 1, A 2, a 3, a 4, a 5,…… , a n

For this array, construct another array b 1, b 2, b 3, b 4, b 5,…… , b, n

Such that array A is the prefix sum of array B, even if a I = b 1 + b 2 +…. + b i

In this case, array B is called the difference of array A

How to construct the b array:

B 1 = a 1, b 2 = a 2 – a 1, b 3 = a 3 – a 2,….. B n = a n- a n-1

You don’t have to do it that way, but if you input array A, you can assume that all the elements of array A and array B are 0. Then insert each time (by adding a constant C to each number in the [L, r] range of array A), e.g

For array a [1,1], add (insert) constant a 1; For the interval [2,2], add the constant a 2,….. In this way, we can quickly construct the difference array B while input array A

The effect of difference:

If we add a constant C to all elements in the range [L, r] of array A, the time complexity is O(n) if we operate on array A directly. If you operate on its difference array B, the time complexity is O(1). This is because the array is an array b prefix and arrays, as long as the b l this element to add C, then a array from l position after all the number can be combined with C, but the r position after all the number C, so we pass to subtract C, b r + 1 this to keep a r position after the number of values in the array.

Thus, adding a constant C to all the numbers in the range [l, r] of array A converts to L plus C for b and r+1 minus C for B.

Practice figure: ACwing-797: difference

// C++
#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int n, m;
int a[N]; // Use an array

// For the interval [l, r], plus the constant c
void insert(int l, int r, int c) {
    // Operate the difference array directly
    a[l] += c;
    a[r + 1] -= c;
}

int main(a) {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) { // Note that the subscript starts at 1
        int t;
        scanf("%d", &t);
        insert(i, i, t); // Create a difference array
    }
    while(m--) {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    // Calculate the difference array prefix sum, restore the original array
    for(int i = 1; i <= n; i++) {
        a[i] += a[i - 1];
        printf("%d ", a[i]); }}Copy the code

Two-dimensional finite difference

The difference matrix

For matrix A, there exists the following matrix B

B 11, B 12, B 13, b 14,……. 1 n, b

B 21, B 22, B 23, B 24,……. 2 n, b

.

.

B m1, B m2, B m3, b m4,….. Mn, b

Such that a ij = the sum of all the numbers in the upper left corner of position [I, j] in matrix B

Call the matrix B the difference matrix of the matrix A.

Similarly, if you expect to add a constant C to all elements in the region of matrix A where the upper left corner is [x1, y1] and the lower right corner is [x2, y2], this can be translated into an operation on its difference matrix B.

Add C to the element at [x1, y1] in b, so that C is added to everything in the lower right corner of [x1, y1] in A, but also to everything beyond [x2, y2]. We need to keep the value constant for the region outside [x2, y2], so we need to subtract. For b x2+1,y1 subtracts C, so the red area is subtracted C, and for B x1,y2+1 subtracts C, so the blue area is subtracted C, and the red area and the blue area overlap, and the overlapping area is subtracted C twice, so you have to add back another C, so for B x2+1,y2+1 plus a C. This completes the process of adding the constant C to all numbers in the [x1, y1], [x2, y2] regions (the green area in the image below).

To sum up, the addition of C to all elements in the region [x1, y1] to [x2, y2] of the original matrix A can be converted to its difference matrix B by the following operation

  • bx1,y1 + C
  • bx1,y2+1 – C
  • bx2+1,y – C
  • bx2+1,y2+1 + C

Simple memory: for [x1, y1] + C, for [x2, y2], x2 + 1, y2 + 1 (on the other axis, y1 and x1), subtract C, and then add C to [x2 + 1, y2 + 1]

Construct matrix B in the same way as above. First, assume that the elements of matrix A and matrix B are all 0, and then matrix B is the difference matrix of matrix A. Insert operations in turn.

Of matrix a [1, 1] to [1, 1], plus a [1] [1], [1, 2] to [1, 2], plus a [1] [2],… , so the matrix B can be constructed

Practice: ACwing-798: Difference matrix

// C++
#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N];
int n, m, q;

void insert(int x1, int y1, int x2, int y2, int c) {
    a[x1][y1] += c;
    a[x2 + 1][y1] -= c;
    a[x1][y2 + 1] -= c;
    a[x2 + 1][y2 + 1] += c;
}

int main(a) {
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i<= n; i++) {
        for(int j = 1; j<= m; j++) {
            int t;
            scanf("%d", &t); insert(i, j, i, j, t); }}while(q--) {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    // Restore the difference matrix to the prefix sum
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
            printf("%d ", a[i][j]);
        }
        printf("\n"); }}Copy the code

Prefix and &difference summary

  • The prefix sum is used to: find the sum of all numbers in any interval, time complexity O(1)

  • Difference is used to add a constant to all numbers in any interval, O(1).

  • Prefix sum and difference are inverts each other

  • Prefix and difference, array subscripts start at 1, so you don’t have to do anything special with boundaries.

We call S the prefix and array of A (matrix), or a the difference array of S (matrix).

A one-dimensional

The prefix sum S I = S I -1 + a I, the sum of any interval [l, r] of array A is S r – S L -1

Insert (int l, int r, int c) insert(int l, int r, int c) insert(int l, int r, int c) At the beginning, we assume that the array S and array A are both 0, and for I = 1~n. Insert (I, I, S[I]), which completes the construction of the difference array A. Insert is defined as follows

void insert(int l, int r, int c) {
    // Add a constant C to all elements of the [l, r] interval of the prefix and array S, just for a[l] + C, for a[r + 1] minus C
    a[l] += c;
    a[r + 1] -= c;
}
Copy the code

A two-dimensional

Prefix and S I,j = S I -1,j + S I,j-1 – S I -1,j-1 + a I,j, The sum of all elements of the matrix A in any interval from [x1, y1] to [x2, y2] is equal to S x2, y2-s x1-1, y2-s x2,y1-1 + S x1-1,y1-1

The simple memory is, the sum of the prefixes of [x2, y2], minus, take the sum of the prefixes of x2, y2 (y1-1, x1-1 on the other axis), minus twice because of the overlap, plus the sum of the prefixes of [x1-1, y1-1]

Difference A, difference I, difference j, it’s also constructed in the same way as one-dimensional difference. Insert (int x1, int y1, int x2, int y2, int c) At the beginning, it is assumed that the S matrix and a matrix are all 0. For each point [I, j], insert(I, j, I, j, S[I][j]) is called every time, that is, the construction of the difference matrix A is completed. Insert is defined as follows

void insert(int x1, int y1, int x2, int y2, int c) {
    a[x1][y1] += c;
    a[x2 + 1][y1] -= c;
    a[x1][y2 + 1] -= c;
    a[x2 + 1][y2 + 1] += c;
}
Copy the code