不包括字符串和图论内容。
某种意义上算是“简单”数据结构……
代码压行警告qwq
如果存在与数据结构有关的经典算法，也会予以列出。
1. 单调队列
const int maxn=1000010;
int n,k,cnt,a[maxn],minans[maxn],maxans[maxn];
deque<int> minint,maxint;
void push(int pos)
{
while(!minint.empty()&&minint.front()<=pos-k)minint.pop_front();
while(!maxint.empty()&&maxint.front()<=pos-k)maxint.pop_front();
while(!minint.empty()&&a[minint.back()]>=a[pos])minint.pop_back();
while(!maxint.empty()&&a[maxint.back()]<=a[pos])maxint.pop_back();
minint.push_back(pos);maxint.push_back(pos);
}
//......
for(int i=1;i<k;i++)push(i);
for(int i=k;i<=n;i++)
{
push(i);cnt++;
minans[cnt]=a[minint.front()];
maxans[cnt]=a[maxint.front()];
}
2. 单调栈
const int maxn=3000010;
int n,a[maxn],ans[maxn];
stack<int> st;
?for(int i=n;i>=1;i--)
{
while(!st.empty()&&a[st.top()]<=a[i])st.pop();
if(!st.empty())ans[i]=st.top();
st.push(i);
}
3. 并查集
路径压缩+按秩合并
const int maxn=100010;
int n,fa[maxn],siz[maxn];
void init(int xx){for(int i=1;i<=xx;i++){fa[i]=i;siz[i]=1;}}
int find(int xx){return fa[xx]==xx?xx:fa[xx]=find(fa[xx]);}
int query(int xx,int yy){return find(xx)==find(yy);}
void merge(int xx,int yy)
{
int fx=find(xx),fy=find(yy);
if(fx==fy)return;
if(siz[fx]<siz[fy]){fa[fx]=fy;siz[fy]+=siz[fx];fa[xx]=fy;}
else{fa[fy]=fx;siz[fx]+=siz[fy];fa[yy]=fx;}
}
4. ST表
int n,m,ans,l,r,k,lg2[100010],st[100010][20];
for(int i=2;i<100010;i++)lg2[i]=lg2[i/2]+1;
for(int i=1;i<=n;i++)scanf("%d",&st[i][0]);
for(int j=1;j<=lg2[n];j++)
for(int i=1;i+(1<<(j-1))<=n;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);k=lg2[r-l+1];
ans=max(st[l][k],st[r-(1<<k)+1][k]);
printf("%d\n",ans);
}
5. 树状数组
5.1 树状数组模板
int n,m,a[500010];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int k){while(x<=n)a[x]+=k,x+=lowbit(x);}
inline int query(int pos)
{
int ans=0;
while(pos)ans+=a[pos],pos-=lowbit(pos);
return ans;
}
5.2 树状数组求逆序对
struct node{int pos,x;}a[500010];
int rk[500010];
bool cmp(node xx,node yy)
{
if(xx.x!=yy.x)return xx.x<yy.x;
return xx.pos<yy.pos;
}
class Bittree
{
public:
int num=500010,datas[500010];
int lowbit(int x){return x&(-x);}
void add(int x,int k){while(x<=num)datas[x]+=k,x+=lowbit(x);}
int query(int pos)
{
int ans=0;
while(pos)ans+=datas[pos],pos-=lowbit(pos);
return ans;
}
}tree;
int n,ans;
//......
for(int i=1;i<=n;i++){scanf("%lld",&a[i].x);a[i].pos=i;}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)rk[a[i].pos]=i;
for(int i=1;i<=n;i++){tree.add(rk[i],1);ans+=i-tree.query(rk[i]);}
6. 线段树
6.1 复杂标记线段树
以线段树2为例。高度模式化的代码。
const int maxn=100010;
int n,m,p,a[maxn];
struct node{int l,r,val,add,mul;}tree[maxn<<2];
void pushup(int x)
{
int lson=x<<1,rson=lson|1;
tree[x].val=(tree[lson].val+tree[rson].val)%p;
}
void pushmul(int x,int k)
{
tree[x].val*=k;tree[x].val%=p;
tree[x].mul*=k;tree[x].mul%=p;
tree[x].add*=k;tree[x].add%=p;
}
void pushadd(int x,int k)
{
tree[x].val+=k*(tree[x].r-tree[x].l+1);tree[x].val%=p;
tree[x].add+=k;tree[x].add%=p;
}
void pushdown(int x)
{
int lson=x<<1,rson=lson|1;
if(tree[x].l==tree[x].r)return;
if(tree[x].mul!=1)//if的先后是按标记的优先级排的
{
pushmul(lson,tree[x].mul);
pushmul(rson,tree[x].mul);
tree[x].mul=1;
}
if(tree[x].add!=0)
{
pushadd(lson,tree[x].add);
pushadd(rson,tree[x].add);
tree[x].add=0;
}
}
void build(int x,int l,int r)
{
tree[x]=(node){l,r,0,0,1};
if(l==r){tree[x].val=a[l];return;}
int mid=(tree[x].l+tree[x].r)>>1,lson=x<<1,rson=lson|1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(x);
}
void modify_mul(int x,int l,int r,int k)
{
pushdown(x);
if(l<=tree[x].l&&r>=tree[x].r){pushmul(x,k);return;}
int mid=(tree[x].l+tree[x].r)>>1,lson=x<<1,rson=lson|1;
if(l<=mid)modify_mul(lson,l,r,k);
if(r>mid)modify_mul(rson,l,r,k);
pushup(x);
}
void modify_add(int x,int l,int r,int k)
{
pushdown(x);
if(l<=tree[x].l&&r>=tree[x].r){pushadd(x,k);return;}
int mid=(tree[x].l+tree[x].r)>>1,lson=x<<1,rson=lson|1;
if(l<=mid)modify_add(lson,l,r,k);
if(r>mid)modify_add(rson,l,r,k);
pushup(x);
}
int query_sum(int x,int l,int r)
{
pushdown(x);
if(l<=tree[x].l&&r>=tree[x].r)return tree[x].val;
int mid=(tree[x].l+tree[x].r)>>1,lson=x<<1,rson=lson|1,ans=0;
if(l<=mid){ans+=query_sum(lson,l,r);ans%=p;}
if(r>mid){ans+=query_sum(rson,l,r);ans%=p;}
return ans;
}