写在前面
数据结构这种东西，还是需要学习一下的。不能投机取巧用STL了，得学会自己手写，毕竟效率差距非常大。
关键是明白原理，然后需要自己手写实践一下，踩坑才行。
代码能力太差，需要多写代码提高。
树形数据结构可能用指针比较多吧。另外那些可以用指针写的数据结构就用指针写。毕竟效率高（可以装逼）
链表
双向链表（最常用的链表，没有之一）
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef struct ListNode{
int data;
ListNode* pre;
ListNode* nxt;
}List;
int length;
List* CreateList(int len)
{
List* ret=(List*)malloc(sizeof(List));
List* tail=ret;
ret->pre=ret,ret->nxt=ret,ret->data=1;
for(int i=2;i<=len;i++)
{
List* newnode=(List*)malloc(sizeof(List));
newnode->data=i,
tail->nxt=newnode,newnode->pre=tail,newnode->nxt=ret,tail=newnode;
}
ret->pre=tail;
length=len;
return ret;
}
void Delete(List* pos)
{
pos->pre->nxt=pos->pre;
pos->nxt->pre=pos->nxt;
free(pos);
length--;
}
List* JumpToItem(List* list,int n)
{
if(n==0) return list;
while(n--)
list=list->nxt;
return list;
}
void Print(List* list)
{
printf("%d ",list->data);
for(int i=2;i<=length;i++)
{
list=list->nxt;
printf("%d ",list->data);
}
printf("
");
}
void InsertAft(List* pos,int data)
{
List* newnode=(List*)malloc(sizeof(newnode));
newnode->data=data,
newnode->pre=pos,newnode->nxt=pos->nxt,pos->nxt=newnode;
length++;
}
void InsertBef(List* pos,int data)
{
pos=pos->pre;
InsertAft(pos,data);
}
int main()
{
List* list=CreateList(15);
Print(list);
Delete(list);
Print(JumpToItem(list,1));
InsertAft(list,233);
Print(JumpToItem(list,1));
InsertBef(JumpToItem(list,2),2333);
Print(JumpToItem(list,1));
return 0;
}
Trie树
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef struct TrieNode{
TrieNode* nxt[26];
bool isStr;
TrieNode(){memset(nxt,NULL,sizeof(nxt));isStr=false;}
}Trie;
inline void insert(Trie* root,char* str)
{
if(root==NULL||str==' ')return;
Trie* p=root;
while(*str!=' ')
{
int pos=*str-'a';
if(p->nxt[pos]==NULL)
{
Trie* newnode=new Trie;
p->nxt[pos]=newnode;
}
p=p->nxt[pos];
++str;
}
p->isStr=1;
}
inline bool search(Trie* root,char* str)
{
Trie* p=root;
while(p!=NULL&&*str!=' ')
{
p=p->nxt[*str-'a'];
++str;
}
return (p!=NULL&&p->isStr==1);
}
inline void del(Trie* root)
{
for(int i=0;i<26;i++)
if(root->nxt[i]!=NULL)del(root->nxt[i]);
delete root;
}
int main()
{
Trie* root=new Trie;
insert(root,"maki");
printf(search(root,"maki")?"1":"0");
return 0;
}
线段树
#include<cstdio>
using namespace std;
const int maxn=2*1e7+10;//5*1e6
long long sum[maxn];//real
long long addv[maxn];//lazy-tag
long long c[maxn/4];
#define mid ((l+r)>>1)
#define lson (o<<1)
#define rson (lson|1)
inline void build(int o,int l,int r)
{
addv[o]=0;
if(l==r)sum[o]=c[l];
else
{
build(lson,l,mid);
build(rson,mid+1,r);
sum[o]=sum[lson]+sum[rson];
}
}
inline void push_down(int o,int l,int r)
{
addv[lson]+=addv[o];
addv[rson]+=addv[o];
sum[lson]+=(mid-l+1)*addv[o];
sum[rson]+=(r-mid)*addv[o];
addv[o]=0;
}
inline void update(int o,int l,int r,int a,int b,int x)
{
if(l>=a&&r<=b)
{
addv[o]+=x;
sum[o]+=(r-l+1)*x;
return;
}
if(addv[o])push_down(o,l,r);
if(a<=mid)update(lson,l,mid,a,b,x);
if(b>mid)update(rson,mid+1,r,a,b,x);
sum[o]=sum[lson]+sum[rson];
}
inline long long query(int o,int l,int r,int a,int b)
{
if(l>=a&&r<=b)return sum[o];
long long ans=0;
if(addv[o])push_down(o,l,r);
if(a<=mid)ans+=query(lson,l,mid,a,b);
if(b>mid)ans+=query(rson,mid+1,r,a,b);
return ans;
}
int n,m,f;
int x,y,k;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)scanf("%d",&c[i]);
build(1,1,n);
for(int i=1; i<=m; i++)
{
scanf("%d",&f);
if(f&1)
{
scanf("%d%d%d",&x,&y,&k);
update(1,1,n,x,y,k);
}
else
{
scanf("%d%d",&x,&y);
printf("%lld
",query(1,1,n,x,y));
}
}
return 0;
}