Algorithm summary

Algorithm summary

1. Difference and prefix and dichotomy

1. Differential

d[i]=a[i]-a[i-1]; // Maintenance difference

d[l]+=k,d[r+1]-=k increases K in the interval of [l,r]

P2367 Chinese achievement - Luogu | new ecology of Computer Science Education (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
int d[5000001];//d[i] indicates a[i]-a[i-1] 
int a[5000001];
int main()
{
	int n,p,x,y,z,i,min=1e9;
	cin>>n>>p;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	
    for(i=1;i<=n;i++)
	{
		d[i]=a[i]-a[i-1];
	}
	for(i=0;i<p;i++)
	{
		cin>>x>>y>>z;
		d[x]+=z;
		d[y+1]-=z;
	}
	
	for(i=1;i<=n;i++)
	{
		a[i]=a[i-1]+d[i];
		if(min>a[i])
		{
			min=a[i];
		}
	}
	cout<<min;
	return 0;
} 

2. Prefix and

P1387 largest square - Luogu | new ecology of Computer Science Education (luogu.com.cn)

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-lsc1fx7b-1651487025423) (C: \ users \ Dell \ appdata \ roaming \ typora user images \ image-20220502165713365. PNG)]

#include <bits/stdc++.h>
using namespace std;
int num[105][105];
int dp[105][105];
int main ()  {
	int n,m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> num[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + num[i][j];
		}
	}
	// i controls the side length of the square and j controls the number of rows 
	int g = min(n,m);
	int maxx = 0;
	int sum = 0;
	for (int e = 1; e <= g; e++) {
		for (int i = e; i <= n; i++) {
			for (int j = e; j <= m; j ++) {
				sum = dp[i][j] - dp[i][j-e] - dp[i-e][j] + dp[i-e][j-e];
				if (sum == e*e) maxx = max(maxx,e); 
			}
		}
	}
	cout << maxx;
}

Dichotomous answer

[P2678 NOIP2015 improvement group] jump the stone - Luogu | new ecology of Computer Science Education (luogu.com.cn)

Idea: binary search + greed

This method is generally used when "the smallest XX of the largest * *" is encountered

First, give an answer by dichotomy and enter the calculation to see whether the answer meets the requirements of the question. If it meets the requirements, it will be further greedy until the optimal solution is obtained

#include <bits/stdc++.h>
using namespace std;
int num[100005];
int len,n,m;
int ans;
bool judge(int x) {
	int d = 0;
	int now = 0;
	for (int i = 1; i <= n+1; i++) {
		if (num[i] - num[now] < x) {
			d++;
		} else {
			now = i;
		}
	}
	if (d > m) return 0;
	else return 1;
}
int main() {
	cin >> len >> n >> m;
	int i;
	for ( i = 1; i <= n; i++) {
		cin >> num[i];
	}
	num[i] = len;
	int l = 0, r = len;
	while (l <= r) {
		int mid = (l+r)/2;
		if (judge(mid)) {
			l = mid + 1;
			ans = mid; 
		} else {
			r = mid-1;
		}
	}
	cout << ans;
}

Divide and conquer and sorting

1. Quick sort

P1177 [template] quick sorting - Luogu | new ecology of Computer Science Education (luogu.com.cn)

#include<bits/stdc++.h>
#defind F(i,n,m) for(int i=n;i<=m;i++)
using namespace std;
int n,a[1000001];
void mysort(int l,int r)//Write your own quick row 
{
    int mid=a[(l+r)/2];//Find the middle number and give 2 points 
    int i=l,j=r;
    do{
        while(a[i]<mid)
		i++;//Find the left half greater than the middle number 
        while(a[j]>mid)
		j--;//Find the one whose right half is less than the middle number 
        if(i<=j)
        {
            swap(a[i],a[j]);//transposition 
            i++;//Shift left pointer to right 
            j--;//Right pointer moves left 
        }
    }
	while(i<=j);
    if(l<j) mysort(l,j);
    if(i<r) mysort(i,r);
}
int main()
{
    cin>>n;
    F(i,1,n)
    cin>>a[i];
    random_shuffle(a+1,a+n+1); //Disrupt it 
    mysort(1,n);//Quick row 
    F(i,1,n)
    cout<<a[i]<<' ';//output 
    return 0;
}

2. Heap sorting

#include<bits/stdc++.h>
#define F(i,n,m) for(int i=n;i<=m;i++)
using namespace std;
int main()
{
	priority_queue<int,vector<int>,greater<int> > q;//Small root pile
	int n,x;
	cin>>n;
	F(i,1,n)
	{
		cin>>x;
		q.push(x);
	}
	F(i,1,n)
	{
		cout<<q.top()<<' ';
		q.pop();
	}
	return 0;
}

3. Bucket sorting

In theory, STL can be used to sort the data in the container, which takes up a lot of space

Upper Code:

#include<bits/stdc++.h>
#define F(i,n,m) for(int i=n;i<=m;i++)
using namespace std;
int main()
{
	map<int,int> a;
	int n;
	cin>>n;
	F(i,1,n)
	{
		int x;
		cin>>x;
		a[x]++;
	}
	map<int,int>::iterator it=a.begin();
	for(it;it!=a.end();it++)
	{
		aa:;
		if(it->second==0) continue;
		cout<<it->first<<' '; it->second--; goto aa;
	}
	return 0;
}

3. Search

1.bfs

Topic details - 7-4 circuit wiring (pintia.cn)

#include <iostream>

\#include <queue>

\#include <cstring>

using namespace std;







int mp[1005][1005], vis[1005][1005], m, n;

int ans[1005][1005];

int ai, aj, bi, bj;

int dx[] = {0, 0, -1, 1};

int dy[] = {1, -1, 0, 0};

queue<pair<int, int>> q;







void bfs() {

   q.push(make_pair(ai, aj));

    vis[ai][aj] = 1; //Tag access

    while (!q.empty()) {

        int x = q.front().first;

        int y = q.front().second;

        q.pop();

        if (x == bi && y == bj) {

            cout << ans[x][y];

            return;

        }

        //Look in four directions

        for (int i = 0; i < 4; ++i) {

            int xx = x + dx[i];

            int yy = y + dy[i];

            //Overflow boundary

            if (xx >= 1 && xx <= m && yy >= 1 && yy <= n) {

                if (!vis[xx][yy] && mp[xx][yy] != 1) {

                    vis[xx][yy] = 1;

                    ans[xx][yy] = ans[x][y] + 1;

                    q.push(make_pair(xx, yy));

                }

            }

        }

    }

}







int main() {

​    ios::sync_with_stdio(false);

​    cin >> m >> n;

​    memset(vis, 0, sizeof(vis));

​    for (int i = 1; i <= m; ++i) {

​        for (int j = 1; j <= n; ++j) {

​            cin >> mp[i][j];

​            ans[i][j] = 1;

​        }

​    }

​    cin >> ai >> aj >> bi >> bj;

​    bfs();

​    return 0;

}

2.dfs

https://pintia.cn/problem-sets/1443552092078542848/problems/1443552633638658050

#include<iostream>

\#include<cstring>

\#include<algorithm>

using namespace std;



int mp[1005][1005], vis[1005][1005], m, n;

int ai, aj, bi, bj;

int ans = 99999999;



void dfs (int x, int y, int cur) {

​    ++cur;

​    if (x > m || x < 1 || y > n || y < 1 || mp[x][y] == 1 || vis[x][y] != 0) {

​        return ;

​    }

​    else if (x == bi && y == bj) {

​        ans = min(ans, cur);

​        return ;

​    }

​    vis[x][y] = 1;

​    dfs(x + 1, y, cur);

​    dfs(x, y + 1, cur);

​    dfs(x - 1, y, cur);

​    dfs(x, y - 1, cur);

​    vis[x][y] = 0;

}



int main() {

​    ios::sync_with_stdio(false);

​    cin >> m >> n;

​    memset(vis, 0, sizeof(vis));

​    for (int i = 1; i <= m; ++i) {

​        for (int j = 1; j <= n; ++j) {

​            cin >> mp[i][j];

​        }

​    }

​    cin >> ai >> aj >> bi >> bj;

​    dfs(ai, aj, 0);

​    cout << ans; 

​    return 0;

}

greedy

P1803 messy yyy / line segment coverage - Luogu | new ecology of Computer Science Education (luogu.com.cn)

#include <bits/stdc++.h> 
using namespace std;
int size;
int ans;
int n,m,x,y;
struct node {
	int st;
	int ed;
};
int num[1000005];
bool cmp(struct node a,struct node b) {
	return a.ed < b.ed;
}
int main()
{
	cin >> n;
	int ll = n;
	int d = 0;
	struct node xd[100005];
	while (n--) {
		cin >> xd[d].st >> xd[d].ed;
		d++;
	}
	sort(xd,xd+ll,cmp);
	int jl = xd[0].ed;
	int ans = 1;
	for (int i = 1; i < ll; i++) {
		if (xd[i].st >= jl) {
			ans++;
			jl = xd[i].ed;
		}
	}
	cout << ans;
}

P1325 radar installation - New Ecology of computer science education in Luogu (luogu.com.cn)

#include <bits/stdc++.h> 
using namespace std;
int num[1005];
struct node {
	double x;
	double y;
};
bool cmp(struct node a,struct node b) {
	return a.y < b.y;
}
int main()
{
	int n,d;
	cin >> n >> d;
	struct node p[100005];
	for (int i = 1; i <= n; i++) {
		int xx,yy;
		cin >> xx >> yy;
		int dis = sqrt(d*d - yy*yy); 
		if (abs(yy) > d) {
			cout << "-1";
			return 0;
		}
		p[i].x = xx - dis;
		p[i].y = dis + xx;
	}
	sort(p+1,p+n+1,cmp);
	int ans = 1;
	double now = p[1].y;
	//double now = sqrt(d*d - p[0].y*p[0].y) + 1.0 * p[0].x;
	//cout << now << endl;
	for (int i = 2; i <= n; i++) {
		//if (p[i].x < 0) int aa = -p[i].x;
		//else aa = p[i].x;
		if ( p[i].x <= now) {
			continue;
		} else {
			now = p[i].y;
			//cout << "now = " << now << endl;
			ans++;
		}
	}
	cout << ans;
}	
// 10 2 4 4-2 = 2

dynamic programming

Classic dp digital triangle

[P1216 USACO1.5][IOI1994] Number Triangles - Luogu | new ecology of Computer Science Education (luogu.com.cn)

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	int a[1005][1005];
	for (int i = 1; i <= n; i++) {
		for (int b = 1; b <= i; b++) {
			cin >> a[i][b];
		}
	}
	int sum = 0;
	for (int i = n-1; i >= 1; i--) {
		for (int b = 1; b <= i; b++) {
			a[i][b] += max(a[i+1][b],a[i+1][b+1]);
		}
	}
	cout << a[1][1];
}

knapsack problem

01 Backpack

[P1048 NOIP2005 popularization group] medicine Collection - Luogu | new ecology of Computer Science Education (luogu.com.cn)

#include <bits/stdc++.h> 
using namespace std;
int num[1005];
int dp[1005];
int main()
{
	int t,m;
	cin >> t >> m;
	int w[1005];
	int val[1005];
	for (int i = 0; i < m; i++) {
		cin >> w[i] >> val[i];
	}
	for (int i = 0; i < m; i++) {
		for (int j = t; j >= w[i]; j--) {
			dp[j] = max(dp[j-w[i]]+val[i],dp[j]);
		}
	}
	cout << dp[t];
}	
// 10 2 4 4-2 = 2

Complete knapsack problem

There are n items, and the weight of each item is w[i], and the value is c[i]. There is a backpack with a capacity of V. ask how to select items and put them into the backpack,

Make the total value in the backpack the largest. There are infinite items of each kind

int dp[N];

//Boundary: DP [0] [v] = 0 or DP [v] = 0; (0<=v<= V)

for(int i=1; i<=n; ++i)

{

​	for(int v= w[i]; v<= V; ++v)//***\*Forward enumeration v\**** 

​		dp[v] = max(dp[v], dp[v-w[i] + c[i]]);

} 

LIS

AT2827 LIS - Luogu | new ecology of Computer Science Education (luogu.com.cn)

#include <bits/stdc++.h>
using namespace std;
int num[1000005];
int main() {
	int n;
	cin >> n;
	int len[1000008];
	for (int i = 1; i <= n; i++) {
		cin >> num[i];
	}
	len[1] = num[1];
	int l = 1;
	for (int i = 2; i <= n; i++) {
		if (num[i] > len[l]) {
			len[++l] = num[i];
		} else {
			int p = upper_bound(len,len+l,num[i]) - len;
			len[p] = num[i];
		}
	}
	cout << l;
}

number theory

Maximum common multiple exgcd

int exgcd(int a,int b) {
    if (a % b == 0) return b;
    else {
        return exgcd(b,a%b);
    }
}

Euler sieve

int ispr[maxn],pri[maxn],p;//ispr[i]=1 means I is not a prime number 
int main()
{
	ispr[0]=ispr[1]=1;
    for (int i = 2;i <= maxn; i++) 
	{
        if (!ispr[i]) 
        pri[++p] = i; //The previous part is the same as the Elsevier sieve. The pri array stores the currently determined prime numbers 
        for (int j = 1; j <=p && i*pri[j] <= maxn; j++)
		 {
            ispr[i*pri[j]] = 1;
            if (i % pri[j] == 0) //If pri[j] is the smallest prime factor of i, i will not be sifted back 
            break;
        }
    }
}

Fast power algorithm

P1226 [template] fast power | remainder operation - New Ecology of computer science education in Luogu (luogu.com.cn)

#include <bits/stdc++.h>
using namespace std;
int mark[10005];
int len[10005];
int l = 0;
long long ans = 1;
int main() {
	long long a,b,p;
	cin >> a >> b >> p;
	long long k = b;
	long long tmp = a;
	while (k) {
		if (k & 1) {
			ans = (ans % p * tmp % p) % p;
		}
		k = k >> 1;
		tmp = (tmp%p * tmp%p) % p;
	}
	cout << a << "^" << b << " mod " << p << "=" << ans;
}

graph theory

Floyd algorithm

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX = 9999999;


int n, e, f[15][15], a, b;



int main() {
    ios::sync_with_stdio(false);
    scanf("%d %d", &n, &e);
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (i == j) {
                f[i][j] = 0;
            }
            else {
                f[i][j] = MAX;
            }
        }
    }
    while (e--) {
        scanf("%d %d", &a, &b);
        f[a][b] = f[b][a] = 1;
    }
    
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
    
    scanf("%d %d", &a, &b);
    if (f[a][b] == MAX) {
        printf("There is no path between %d and %d.", a, b);
    }
    else {
        printf("The length of the shortest path between %d and %d is %d.", a, b, f[a][b]);
    }
    return 0;
}

Naive dijkstra algorithm

Chain forward star

(60 messages) chain forward star (detailed explanation)_ Stephen Curry's csdn blog_ Chain forward star

void add(int u,int v,int w)
{
    edge[cnt].w = w;
    edge[cnt].to = v;
    edge[cnt].next = head[u]; //
    head[u] = cnt++;
}
#include<bits/stdc++.h>

using namespace std;

long long n, m, s, be[500001], en[500001], len[500001], jour[10001];

int main() {
        cin >> n >> m >> s;
        for(int i = 1; i <= m; ++i)
                cin >> be[i] >> en[i] >> len[i];
        for(int i = 1; i<= n; ++i)
                jour[i] = 2147483647;
        jour[s] = 0;
        for(int i = 1; i <= n-1 ; ++i) {
                int flag = 0;
                for(int j = 1; j <= m; ++j) {
                        if(jour[en[j]] > jour[be[j]] + len[j]) {
                                jour[en[j]] = jour[be[j]] + len[j];
                                flag = 1;
                        }
                }
                if(!flag)
                        break;
        }
        for(int i = 1; i<= n; ++i)
                cout << jour[i] << " ";
        return 0;
}

Dijkstra queue optimization

#include<bits/stdc++.h>
using namespace std;


int n, m, s, u, v, w;
int be[200001] = {0}, en[200001], nex[200001], len[200001];
int dis[200001], flag[200001] = {0};
priority_queue< pair<int,int> > q;


int main() {
    cin >> n >> m >> s;
    for(int i = 1; i <= m; ++i) {
        cin >> u >> v >> w;
        en[i] = v;
        nex[i] = be[u];
        be[u] = i;
        len[i] = w;
    }


    for(int i = 1; i <= n; ++i)
        dis[i] = 1e10;
    dis[s] = 0;
    q.push(make_pair(0,s));
    while(!q.empty()) {
        int now = q.top().second;
        q.pop();
        if(flag[now])
            continue;
        flag[now] = 1;
        int temp = be[now];
        while(temp) {
            if(dis[en[temp]] > dis[now] + len[temp]) {
                dis[en[temp]] = dis[now] + len[temp]; // slack
                q.push(make_pair(-dis[en[temp]], en[temp]));
            }
            temp = nex[temp];
        }
    }
    for(int i = 1; i <= n; ++i)
        cout << dis[i]  << " ";
    return 0;
}

Tree array Fenwick tree (from she Jie)

1, Introduce

  • Tree array is a data structure used to dynamically query interval information and support modification

    Using lowbit technology, the core operation of tree array can be completed in a few short steps, so its code efficiency is much higher than that of line segment tree. In addition, when the problem is extended to the high-dimensional case, the high-dimensional tree array has more advantages than the high-dimensional line segment tree.

    lowbit(x): find the lowest 1 and subsequent 0 under binary X;

  • Problem form of one-dimensional tree array:

    Given an array a[1... n], the following two operations are supported:

    ​ 1. Modify: add v to a[i]

    ​ 2. Query: find the sum of a[1] + a[2] +... + a[i]

2, Thought

For a general binary tree, we draw it like this

Moving the position slightly is the drawing method of tree array

  • Here is the structure diagram of a tree array:

    t[x] save the sum of node values in the subtree with X as the root

    Black represents the value a[i] corresponding to its own root (subscript),

    Gray represents the value a[k... i - 1] corresponding to the leaf node (other subscripts) to be maintained,

    The whole bar represents the sum of the leaf node values in the subtree with it as the root (that is, the elements of the a array contained in the "subset"),

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-vfyahzie-1651487025429) (C: \ users \ Dell \ appdata \ roaming \ typora user images \ image-20220502181719958. PNG)]

  • How should these subtrees (subsets) be divided?

    It can be found that:

    1. The number of zeros at the end of each layer is the same, and the number of zeros is related to the length of its coverage;
    2. The binary of the number of elements in t[x] is the number corresponding to the position of the lowest 1 in the binary representation of the X subscript;
    3. t[x] node records the interval information of interval [x-lowbit(x) + 1, x], and its coverage length is lowbit(x);
    4. The parent node of t[x] node is t[x + lowbit(x)];

    In addition:

    The intervals recorded by the child nodes of t[i] do not cover each other, and the intervals [x-lowbit(x) + 1, x] are covered from small to large

    A node I is only overwritten by node i and its ancestors

    The depth of the whole tree is log З n + 1

    subscript12345678
    Subscript binary110111001011101111000
    content11...21...21...455...671...8
    Number of elements12141218
    Binary number of elements110110011011000
    • How to find the number corresponding to the lowest binary 1 of a number x

    Simple method: enumeration. Every time the module is 2, when the remaining 1, the lowest non-0 bit O (log ν X) will be found

    Better method: lowbit() function: it represents the value composed of the lowest 1 and the following 0 of non negative integer in binary representation

    eg. lowbit(6) = lowbit( (0110)₂ ) = (10)₂ = 2

    First, reverse 0110 to get 1001, and then add 1 to get 1010

    It can be found that except for the lowest 1 and the following 0, the other bits are different from the original number

    Finally, for the bitwise sum of two digits (0110 ^ 1010), 0010 is obtained

    Because the value stored by the computer uses complement, the value after taking the inverse + 1 is the negative number

    So lowbit (x) = x & (~ x + 1) = x & - x

    int lowbit(int x)
    {
        return x & (-x);
    }
    

3, One dimensional establishment

  • Simple approach:

    Insert one by one: O(n log ν n) -- equivalent to n modification operations

void build()
{ 
    for (int i = 1; i <= MAX_N; i++)
    {
        for (int j = i ; j >= i - lowbit(i); j--)
            t[i] += A[j];
    }
}
  • Optimization practices:

    Maintain a prefix and array, pre [x] = t (a [1... X]), t [x] = pre [x] - pre [x - lowbit (x)]

    (t[x] maintains [x-lowbit(x) + 1, x], so reduce pre to initialize the tree array in linear complexity)

4, One dimensional single point modification + query

When adding d to A[i], you need to pay attention to which subset contains the element A[i] that needs to be modified

Therefore, it is necessary to update the subset of lowbit(i) larger than i circularly, because the depth of the tree is log ν MAX_N. Therefore, the modified depth is log З MAX_N

The modification process is to add the lower 1 under binary each time (101 + 1 - > 110, 110 + 10 - > 1000)

void add(int x, int d)
{ 
    for (int i = x; i <= MAX_N; i += lowbit(i))
        t[i] += d;
}

In the query process, the lower 1 in the binary is removed every time (1111 - 1 - > 1110, 1110 - 10 - > 1100, 1100 - 100 - > 1000)

int ask (int x)
{
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i))//First: for
        ans += t[i];
    return ans;
    
    //while(i>0) ans += t[i], i -= lowbit(i);  Second: while
}

The following figure shows a query tree:

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-ridgz3bq-1651487025430) (C: \ users \ Dell \ appdata \ roaming \ typora \ typora user images \ image-20220502181753952. PNG)]

1. Query interval and A[x... y]

Only ask(y) - ask(x - 1) needs to be calculated

Topic details - L2-3 interval prime number (25 points) (pintia.cn)

2. Single point query A[x]

The simplest method is ask(x) - ask(x - 1), but you need to execute the query twice

but it can be observed that a [x] = t [x] - (ask (x - 1) - ask (LCA (x, x-1)), you only need to calculate the value from X-1 to the nearest common ancestor LCA, without performing two queries

eg. a[12] = t[12] - ( ask(11) - ask(8) )

  • Nearest common ancestor LCA = x - lowbit(x)
get_value(x){
   int ans = t[x];
   int LCA = x - lowbit(x);
    x--;
    while(x != LCA){
        ans -= t[x];
        x -= lowbit(x);
    }
    return ans;
}//Single point query

3. Assuming that the element is nonnegative, query the prefix subscript m corresponding to a prefix k and v

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-poas76qr-1651487025430) (C: \ users \ Dell \ appdata \ roaming \ typora \ typora user images \ image-20220502181829803. PNG)]

  • You can also do a bisection directly on the tree array

    • Because the subset of power with subscript 2 contains all elements from the beginning to itself, we can divide it in two according to the update tree, and the initial step size is MAX_N. Then halve each time

The following figure shows the update tree:

[the external chain image transfer fails, and the source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-6qelqamq-1651487025430) (C: \ users \ Dell \ appdata \ roaming \ typora user images \ image-20220502181841386. PNG)]

get_index(k){
   int m = 0;
   int len = MAX_N;
    while(len){
        test_i = m + len;
        if(k >= t[test_i]){
			m = test_i;
            k -= t[text_i];
        }
        len /= 2;
    }
    return m;
} 

5, One dimensional interval modification, single point query

  • Question form:

    Maintain an array a[1... n] with length n, and support two operations:

    C l r d add a[l... r] to d

    Q l r asks the sum of a[l... r]

    ​ 1 <= n, Q <= 1 0 5 10^5 105

  • A differential array b is introduced, and the tree array is used to maintain the prefix and sum of d, that is, to maintain the increment of each element of a []

b[i] = a[i] - a[i-1]; a[i] = sum(b[1...i]); b[l] += d, b[r+1] -= d

  • Query a[x]:

ans = a[x] + ask(x) (when querying the single point value a[x], use the initial value plus the increment of a[x], that is, ask(x))

  • **Modify * * [l, R] + D:

    ​ add(l, d) add(r+1, -d)

According to the definition of b[i] array, just give! [b[i] array definition, just givePlus x, here Subtract x)

void range_add(int l, int r, int d){ //Add d to interval [l, r]
    add(l, d), add(r + 1, -d);
}
void add(int x, int d){ //This function is used to modify directly in the tree array
    while(x <= n) t[x] += x, x += lowbit(x);
}
int ask(int x){ //Single point query
    int ans = 0;
    while(x) ans += t[x], x -= lowbit(x);
    return ans;
}

6, One dimensional interval modification, interval query

  • Question form:

    Maintain an array a[1... n] with length n, and support two operations:

    C l r c adds c to all a[l... r]

    Q l r asks the sum of a[l... r]

    ​ 1 <= n, Q <= 1 0 5 10^5 105

The idea of differential array requires the increment of the prefix sum of [1... X] elements in the a[x] array

∑ i = 1 x b [ i ] → a [ x ] increase amount \sum_{i=1}^xb[i] → a[x] increment i=1 Σ x b[i] → a[x] increment

∑ i = 1 x ∑ j = 1 i b [ i ] → a [ x ] front Affix and of increase amount \sum_{i=1}^x\sum_{j=1}^ib[i] → a[x] increment of prefix sum i=1 Σ x j=1 Σ I b[i] → increment of a[x] prefix sum (preprocessing a[x] prefix and sum[x])

Formula: ∑ i = 1 x ∑ j = 1 i b [ i ] \sum_{i=1}^x\sum_{j=1}^ib[i] ∑i=1x​∑j=1i​b[i] = ( x + 1 ) ∑ i = 1 x b [ i ] (x+1)\sum_{i=1}^x{b[i]} (x+1)∑i=1x​b[i] - ∑ i = 1 x i ∗ b [ i ] \sum_{i=1}^xi * {b[i]} ∑i=1x​i∗b[i]

The blue shadow in the figure is the desired color

[the external chain image transfer fails, and the source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-z9zrx4af-1651487025431) (C: \ users \ Dell \ appdata \ roaming \ typora user images \ image-20220502181900692. PNG)]

  • Set two tree arrays: t1 maintains the b[i] prefix sum, and t2 maintains the i * b[i] prefix sum

  • Sum of query [l, r]

    Prefix sum of position x = (x + 1) * t1[x] - t2[x]

    Sum of interval [l, r] = prefix of position r and - prefix sum of position L-1 = (sum[r] + ask ® ) - (sum[l-1] + ask(l-1) )

  • Modify [l, R] + D

add(l, l**d) add(r+1, - (r+1)*d)

void add(ll p, ll x){
    for(int i = p; i <= n; i += lowbit(i))
        t1[i] += x, t2[i] += x * p;
}
void range_add(ll l, ll r, ll x){
    add(l, x), add(r + 1, -x);
}
ll ask(ll p){
    ll ans = 0;
    for(int i = p; i; i -= lowbit(i))
        ans += (p + 1) * t1[i] - t2[i];
    return ans;
}
ll range_ask(ll l, ll r){
    return ask(r) - ask(l - 1);
}

7, Find the maximum value of one-dimensional interval

1. Update after single point modification

The interval [1, n] needs to be initialized:

void update(int x, int val)
{
	while (x <= n)
	{
        //sum[x] += d; Single point modification 
		h[x] = max(h[x], val);
		x += lowbit(x);
	}
}//When you want to update a number, clear h [] and use a [] to update h [] 

Time complexity O (n * log n).

[the external chain image transfer fails, and the source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-ll8iaa5l-1651487025431) (C: \ users \ Dell \ appdata \ roaming \ typora \ typora user images \ image-20220502181922681. PNG)]

Example: if x = 1010000

= 1001000 + lowbit(1001000) = 1001000 + 1000 = 1001000 + 2^3

= 1001100 + lowbit(1001100) = 1001100 + 100 = 1001100 + 2^2

= 1001110 + lowbit(1001110) = 1001110 + 10 = 1001110 + 2^1

= 1001111 + lowbit(1001111) = 1001111 + 1 = 1001111 + 2^0

Therefore, an algorithm similar to the maintenance interval sum algorithm of tree array can be obtained:

void update(int x)
{
	while (x <= MAX_N)
	{
		h[x] = a[x];
		for (int i = 1; i < lowbit(x); i <<= 1)
			h[x] = max(h[x], h[x-i]);//For each [i]
		x += lowbit(x);
	}
}

Therefore, for each h[i], on the premise of ensuring that h[1... x-1] is correct, the time complexity to recalculate the value of h[x] is O(log n)

2. Maximum value of query interval

Let query(x,y) represent the maximum value of the query [x, y] interval, and h[y] represent the maximum value of [y-lowbit(y)+1, y].

Therefore, it can be solved as follows:

If y-lowbit (y) > x, then query (x, y) = max (H [y], query (x, y-lowbit (y));

If y-lowbit (y) < = x, then query (x, y) = max (a [y], query (x, Y-1);

Time complexity is O()

int query(int x, int y)
{
	int ans = 0;
	while (y >= x)
	{
		ans = max(a[y], ans);
		y--;
		for (; y-lowbit(y) >= x; y -= lowbit(y))
			ans = max(h[y], ans);
	}
	return ans;
}

Title details - 7-7 mouth strong king (pintia.cn)

	h[x] = max(h[x], val);
	x += lowbit(x);
}

}//When you want to update a number, clear h [] and use a [] to update h []

Time complexity O(n * log n). 



[External chain picture transfer...(img-ll8IAa5l-1651487025431)]

> give an example:	if x = 1010000
>
> = 1001000 + lowbit(1001000) = 1001000 + 1000 = 1001000 + 2^3
>
> = 1001100 + lowbit(1001100) = 1001100 + 100 = 1001100 + 2^2
>
> = 1001110 + lowbit(1001110) = 1001110 + 10 = 1001110 + 2^1
>
> = 1001111 + lowbit(1001111) = 1001111 + 1 = 1001111 + 2^0

Therefore, an algorithm similar to the maintenance interval sum algorithm of tree array can be obtained:

```c++
void update(int x)
{
	while (x <= MAX_N)
	{
		h[x] = a[x];
		for (int i = 1; i < lowbit(x); i <<= 1)
			h[x] = max(h[x], h[x-i]);//For each h[i]
		x += lowbit(x);
	}
}

Therefore, for each h[i], on the premise of ensuring that h[1... x-1] is correct, the time complexity to recalculate the value of h[x] is O(log n)

2. Maximum value of query interval

Let query(x,y) represent the maximum value of the query [x, y] interval, and h[y] represent the maximum value of [y-lowbit(y)+1, y].

Therefore, it can be solved as follows:

If y-lowbit (y) > x, then query (x, y) = max (H [y], query (x, y-lowbit (y));

If y-lowbit (y) < = x, then query (x, y) = max (a [y], query (x, Y-1);

Time complexity is O()

int query(int x, int y)
{
	int ans = 0;
	while (y >= x)
	{
		ans = max(a[y], ans);
		y--;
		for (; y-lowbit(y) >= x; y -= lowbit(y))
			ans = max(h[y], ans);
	}
	return ans;
}

Title details - 7-7 mouth strong king (pintia.cn)

Tags: C++ Algorithm

Posted by Toggles on Tue, 03 May 2022 11:40:25 +0300