자료구조/알고리즘 공부 소감-5

近况(근황)

昨天我复习了一下前缀和还有差分，然后今天复习了一下线段树和树状数组。这些东西去年寒假时候都学过，但是现在都忘记了TT。
어제 저는 누적합과 차분배열을 복습했습니다.그리고 오늘 조금 세그먼트 트리와 펜윅 트리를 복습했습니다. 예전에는 모두 공부했었지만 이제 전혀 생각이 못 납니다.ㅠㅠ.

前缀和(누적합)

먼저 누적합은 특정한 배열이 있을 때, 해당 배열까지의 합을 나타내는 말이다.이는 누적합의 경우 미리 계산 해둘 수 있기 때문이다.나는 보통 아래와 같은 코드를 쓰는 편이다.

// 누적합 씨플플 코드
vector<int>v;
vector<int>sums;   // 누적합 배열
int n;

int query(int l,int r){
	return sums[r]-sums[l-1];
}

void solve(){
	cin>>n;
   	v.resize(n);
    sums.resize(n+1);
    for (int i = 0;i < n;i++){
    	cin>>v[i];
        sums[i+1] = v[i]+sums[i];
    }
    
    cout<<query(1,4)<<"\n";
}

差分数组(차분배열)

근데 아무것도 없다.

线段树(세그먼트 트리)

线段树比树状数组复杂得多，我的建议是我自己先死记硬背。
이 템플릿은 구간 업데이트와 구간 합 쿼리,그리고 지연 갱신의 상향/하향 전파 기능을 제공한다.以下是需要死记硬背的部分:

• 懒标记的上推和下推:

void push_up(int node){
	tree[node] = tree[2*node]+tree[2*node+1]; 
    // 使用左右子节点的值来更新父节点的值。
}
void push_down(int node,int l,int r){
	if (lazy[node] == 0) return;
    // 如果懒标记值为0就直接返回。
    int mid = l+(r-l)/2;
    tree[2*node]+=lazy[node]*(mid-l+1);         // 严格注意这个倍数
    lazy[2*node] += lazy[node];
    tree[2*node+1]+=lazy[node]*(right-(mid+1)+1);
    lazy[2*node+1]+=lazy[node];
    lazy[node] = 0;// 下推完懒标记清零
}

• 线段树tree数组的初始化:

void build(int node,int l,int r){
    if (l == r){
        tree[node] = arr[l];    // l == r意味着区间只有一个元素，也就是就一个东西，那我直接往上一放就行。
    }
    int mid = l+(r-l)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    push_up(node);
}

• 구간 업데이트 구현. 즉, 모든 원소에 val정도로 증가시킨다:

void update(int node,int l,int r,int ql,int qr,int val){
    // 如果说待更新区间把当前区间完全包含其中，就加上val
    if (ql <= l&&qr>=r){
        // 这里的ql和qr表示的是"이상/이하"而不是超过，未满。
        tree[node]+=(r-l+1)*val;   // 同建树
        lazy[node]+=val;            // 同建树
        return ;  // 不懂这里为什么返回
    }
    // 保证子节点数据是最新的
    push_down(node,l,r);
    int mid = l+(r-l)/2;  
    // 不懂这里为什么是이하而不是미만
    if (ql <= mid) update(2*node,l,mid,ql,qr,val); 
    if (qr > mid)update(2*node+1,mid+1,r,ql,qr,val);
    push_up(node);
    // 丸暗记:再次更新父节点的值
}

• 구간 합 쿼리 구현:

long long query(int node,int l,int r,int ql,int qr){
    // 전체적으로 업데이트와 같죠?
    if (ql<= l&&qr  >=r){
        return tree[node];
    }
    push_down(node,l,r);    // 하향 전파는 최신 데이터를 이용하도록 하는 조작이다.
    int mid = l+(r-l)/2;
    long long sum = 0;
    if (ql <= l) sum+=query(node*2+,l,mid,ql,qr);
    if (qr > r) sum+=query(node*2+1,mid+1,r,ql,qr);
    return sum;
}

我个人对于线段树有一些理解:首先是函数形参中的node和l还有r，区间[l,r]其实就是node节点表示的区间。这是一个底层的规则，在函数体中计算mid时，也要遵循这个规则在调用递归时表达子区间。

没用的(딴소리)

这几个常用的数据结构和算法都涉及到了时间复杂度低于O(n)的区间操作。虽然基于的思想并不同，但是我还是把这几个写在了一起。整体来讲相比于图论的复杂算法还是比较简单的。
앞으로도 알고리즘을 잘 구사하도록 최선을 다하겠습니다.