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
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
#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
#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
#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
#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
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:
- 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;
- 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;
- t[x] node records the interval information of interval [x-lowbit(x) + 1, x], and its coverage length is lowbit(x);
- 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
subscript 1 2 3 4 5 6 7 8 Subscript binary 1 10 11 100 101 110 111 1000 content 1 1...2 1...2 1...4 5 5...6 7 1...8 Number of elements 1 2 1 4 1 2 1 8 Binary number of elements 1 10 1 100 1 10 1 1000 - 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 give
Plus 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=1ib[i] = ( x + 1 ) ∑ i = 1 x b [ i ] (x+1)\sum_{i=1}^x{b[i]} (x+1)∑i=1xb[i] - ∑ i = 1 x i ∗ b [ i ] \sum_{i=1}^xi * {b[i]} ∑i=1xi∗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;
}